Relevant Books

For more background in statistics check out the following books:

All presented material is under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Install and load packages

# Clear the workspace
rm(list = ls())
# List of package needed for this workshop
reqpkg <- c("ggplot2","jpeg", "Rtsne", "randomForest", "MASS")
# Check if the packages are installed:
inpkg = installed.packages()[, "Package"] #installed packages
neededpkg = reqpkg[!reqpkg %in% inpkg]
if(length(neededpkg) > 0){
  stop(paste("\n Need to install the following package:", neededpkg))
}

If you haven’t done that already, download the workshop materials:

url_to_class_materials <- "https://stanford.box.com/s/sqmpjdbuxa29a8fenm1cqxc0ri6c3276"
# Change the path directory and uncomment the line below
#setwd("/path/to/dir/")
download.file("url_to_class_materials", "R_workshop.zip")
unzip("R_workshop.zip")

Statistical Modeling

Why do you need a model? You would like to:

In this workshop you won’t learn mathematical details about how the methods present work or how to create a good statistically-sound model. I will just equip you with the knowledge of how to use some of the R packages that implement the more popular statistical techniques, and how to interpret their outputs.

You can check out other workshops e.f statistical learning or machine learning to learn more on theory these methods are based on.

To illustrate how statistical modelling works in R we will use the mtcars, built-in dataset, that comes from a 1974 issue of Motor Trends magazine.

data("mtcars")
head(mtcars)
                   mpg cyl disp  hp drat    wt  qsec vs am gear carb
Mazda RX4         21.0   6  160 110 3.90 2.620 16.46  0  1    4    4
Mazda RX4 Wag     21.0   6  160 110 3.90 2.875 17.02  0  1    4    4
Datsun 710        22.8   4  108  93 3.85 2.320 18.61  1  1    4    1
Hornet 4 Drive    21.4   6  258 110 3.08 3.215 19.44  1  0    3    1
Hornet Sportabout 18.7   8  360 175 3.15 3.440 17.02  0  0    3    2
Valiant           18.1   6  225 105 2.76 3.460 20.22  1  0    3    1

Hypothesis testing

One often asked question in data analysis is whether there is a significant difference between two samples, or groups. For example, one be interested in whether a group of patients subject to a medical treatment had better outcomes than a control group. These kinds of hypotheses can be tested with statistical procedures.

Here we will show how to perform a Student’s T-test, which is one of the methods statisticians traditionally use to test the equality of the means of two populations.

Hypothesis test: example

Analyzing our example dataset we might be interested whether the fuel efficiency, i.e. mileage per gallon is different for the cars with automatic and manual transmission. The example and the code in the following testing and and linear regression sections is adapted from the one found here.

First we can visualize the observations using the boxplot. Th data about the transmission is stored in the am column and on the fuel efficiency in the mpg column.

data("mtcars")
mtcars$am <- factor(mtcars$am, levels = c(0, 1), 
                    labels = c("automatic", "manual"))
ggplot(mtcars, aes(x = am, y = mpg)) + geom_boxplot() +
  xlab("Trasmission") + ylab("Fuel efficiency")

To test whether the mean mileage per gallon is different between the cars with automatic and manual transmission, we can use the t.test() function:

(tt <- t.test(mpg ~ am, data=mtcars))

    Welch Two Sample t-test

data:  mpg by am
t = -3.7671, df = 18.332, p-value = 0.001374
alternative hypothesis: true difference in means is not equal to 0
95 percent confidence interval:
 -11.280194  -3.209684
sample estimates:
mean in group automatic    mean in group manual 
               17.14737                24.39231 

Here the first argument is the formula = mpg ~ am. In R a tilde symbol, ~ means “explained by”. That is we want to test the miles per gallon explained by the automatic transmission. The second argument is the dataset we choose, mtcars.

We can extract the information computed for the t-test stored in the following elements of tt.

names(tt)
[1] "statistic"   "parameter"   "p.value"     "conf.int"    "estimate"    "null.value"  "alternative" "method"      "data.name"  

We can extract the p-value, that is the probability that we would observe a more extreme difference in the sample means given that both samples come from the same population. In this case it means that if indeed the automatic and manual transmission cars have equal average mileage per gallon rate, then the probability that we would observe a greater or equal difference in the sample mean mtg is equal to p-value.

tt$p.value
[1] 0.001373638

The 95% confidence interval for the difference between the two means is stored in:

tt$conf.int
[1] -11.280194  -3.209684
attr(,"conf.level")
[1] 0.95

Supervised Learning

Regression

Linear Regression

  • Linear regression is a type of regression where the quantitative output variable is modeled as a linear function of the inputs.

  • Simple linear regression predicts the output \(y\) from a single predictor \(x\). That is we assume the outcome \(y\) follows the following linear model, where \(\epsilon\) is a random noise term with zero mean.

\[y = \beta_0 + \beta_1 x + \epsilon\]

  • Multiple linear regression assumes \(y\) relies on many covariates:

\[y = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + \dots + \beta_p x_p + \epsilon = \vec \beta \cdot \vec x + \epsilon\]

Linear regression seeks a solution \(\hat y = \hat \beta \cdot \vec x\) such that the difference between the true outcome \(y\) and the prediction \(\hat y\) (the sum of the squared residuals) is minimized.

\[arg \min\limits_{\hat \beta} \sum_i \left(y^{(i)} - \hat \beta x^{(i)}\right)^2\]

Simple Linear Regression

Analyzing the example dataset mtcars, we can try to model the mileage per gallon using the weight of the car. That is we would like to use the weight of the car to predict the mpg.

In R the linear models can be fit using an lm function.

fit <- lm(mpg ~ wt, mtcars)

Note that we use the same notation as for the t.test function. We can check the details on the fitted model by calling:

summary(fit)

Call:
lm(formula = mpg ~ wt, data = mtcars)

Residuals:
    Min      1Q  Median      3Q     Max 
-4.5432 -2.3647 -0.1252  1.4096  6.8727 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)  37.2851     1.8776  19.858  < 2e-16 ***
wt           -5.3445     0.5591  -9.559 1.29e-10 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 3.046 on 30 degrees of freedom
Multiple R-squared:  0.7528,    Adjusted R-squared:  0.7446 
F-statistic: 91.38 on 1 and 30 DF,  p-value: 1.294e-10

The results are organized as follows: * Call – the function call for the fitted model, * Residuals – the residuals between the true mpg and the predicted values * Coefficents – the fitted coefficients for the fitted model (the \(\beta\)’s in the linear model formula). The values, the standard errors, the t-statistics as well as the p-values are shown. The stars in the last column mark the significance of each coefficient (more stars means more importance). * Other details on the performance of the model.

Coefficients of the model can be extracted with:

(co <-  coef(summary(fit)))
             Estimate Std. Error   t value     Pr(>|t|)
(Intercept) 37.285126   1.877627 19.857575 8.241799e-19
wt          -5.344472   0.559101 -9.559044 1.293959e-10

To predict the mpg for the existing observations (cars) you can call

predict(fit)
          Mazda RX4       Mazda RX4 Wag          Datsun 710      Hornet 4 Drive   Hornet Sportabout             Valiant          Duster 360 
          23.282611           21.919770           24.885952           20.102650           18.900144           18.793255           18.205363 
          Merc 240D            Merc 230            Merc 280           Merc 280C          Merc 450SE          Merc 450SL         Merc 450SLC 
          20.236262           20.450041           18.900144           18.900144           15.533127           17.350247           17.083024 
 Cadillac Fleetwood Lincoln Continental   Chrysler Imperial            Fiat 128         Honda Civic      Toyota Corolla       Toyota Corona 
           9.226650            8.296712            8.718926           25.527289           28.653805           27.478021           24.111004 
   Dodge Challenger         AMC Javelin          Camaro Z28    Pontiac Firebird           Fiat X1-9       Porsche 914-2        Lotus Europa 
          18.472586           18.926866           16.762355           16.735633           26.943574           25.847957           29.198941 
     Ford Pantera L        Ferrari Dino       Maserati Bora          Volvo 142E 
          20.343151           22.480940           18.205363           22.427495 

To predict the mpg for the new observations, e.g. cars with specific weights, e.g. wt = 3.14 we can use the computed coefficients:

co[, 1]
(Intercept)          wt 
  37.285126   -5.344472 
# beta0 + beta1 * wt
co[1, 1] + co[2, 1]* 3.14 #  37.285126 +  (-5.344472) * 3.14
[1] 20.50349

We can make predictions for a large number of new observations by creating a data frame with new weights:

newcars <- data.frame(wt = c(2, 2.1, 3.14, 4.1, 4.3))
predict(fit, newcars)
       1        2        3        4        5 
26.59618 26.06174 20.50349 15.37279 14.30390 

Note that this produces the same prediction for wt = 3.14 as we computed previously.

We can plot the data and the fitted model using ggplot2. This can be done even without computing the model in the previous step.

The geom_smoother with the method argument set equal to "lm" does the computations automatically.

ggplot(mtcars, aes(wt, mpg)) + geom_point() + geom_smooth(method="lm")

Multiple Linear Regression

More elaborate models involving more input variables can be fitted using the same function lm().

For example we can be interested in predicting the mpg from weight, displacement and the number of cylinders in the car.

Look at the data:

ggplot(mtcars, aes(x=wt, y=mpg, col=cyl, size=disp)) + geom_point()

mfit1 <- lm(mpg ~ wt + disp + cyl, data = mtcars)
summary(mfit1)

Call:
lm(formula = mpg ~ wt + disp + cyl, data = mtcars)

Residuals:
    Min      1Q  Median      3Q     Max 
-4.4035 -1.4028 -0.4955  1.3387  6.0722 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) 41.107678   2.842426  14.462 1.62e-14 ***
wt          -3.635677   1.040138  -3.495  0.00160 ** 
disp         0.007473   0.011845   0.631  0.53322    
cyl         -1.784944   0.607110  -2.940  0.00651 ** 
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 2.595 on 28 degrees of freedom
Multiple R-squared:  0.8326,    Adjusted R-squared:  0.8147 
F-statistic: 46.42 on 3 and 28 DF,  p-value: 5.399e-11

The same commands as before can be applied to summary(mfit1) to extract the information.

To predict mpg for new values cars first create a data frame of new inputs per car:

newcars <- data.frame(wt = c(2, 2.1, 3.14, 4.1, 4.3),
                      disp = c(100, 200, 500,300, 210),
                      cyl = c(6,6,4,6,8))
predict(mfit1, newcars)
       1        2        3        4        5 
23.87395 24.25768 26.28834 17.73362 12.76403 

Models with interaction effects can be specified with *:

mfit2 <- lm(mpg ~ am * wt, mtcars)
summary(mfit2)

Call:
lm(formula = mpg ~ am * wt, data = mtcars)

Residuals:
    Min      1Q  Median      3Q     Max 
-3.6004 -1.5446 -0.5325  0.9012  6.0909 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)  31.4161     3.0201  10.402 4.00e-11 ***
ammanual     14.8784     4.2640   3.489  0.00162 ** 
wt           -3.7859     0.7856  -4.819 4.55e-05 ***
ammanual:wt  -5.2984     1.4447  -3.667  0.00102 ** 
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 2.591 on 28 degrees of freedom
Multiple R-squared:  0.833, Adjusted R-squared:  0.8151 
F-statistic: 46.57 on 3 and 28 DF,  p-value: 5.209e-11

Lasso Regression

Nowadays, working with real datasets we can encounter a problem of having “too” many variables. One example of such a problem is prediction the risk of a disease based on the single nucleotide polymorphisms (SNPs) data. In this case the number of predictions can be much larger than than the number of observations. Lasso regression is especially useful for problems, where the number of available covariates is extremely large, but only a handful of them are relevant for the prediction of the outcome.

Lasso is simply regression with \(L_1\) penalty. That is we are interested in finding a solution to the following problem:

\[arg \min\limits_{\hat \beta} \sum_i \left(y^{(i)} - \hat \beta x^{(i)}\right)^2 + \lambda \|\hat \beta\|_1\]

It turns out that the \(L_1\) norm \(\|\vec x\|_1 = \sum_j |x_j|\) promotes sparsity which means that the solutions found will usually have only a small number of non-zero coefficients. The number of non-zero coefficients depends on the choice of the tuning parameter, \(\lambda\). The higher the \(\lambda\) the fewer non-zero coefficients.

Lasso regression is implemented in an R package glmnet. An introductory tutorial to the package can be found here.

Lasso Example

We again use the mtcars datasets for the following example. Now we will build a model predicting the mpg using the Lasso regression. We supply all the available covariates and let the algorithm figure out fit

library(glmnet)
head(mtcars)
                   mpg cyl disp  hp drat    wt  qsec vs        am gear carb
Mazda RX4         21.0   6  160 110 3.90 2.620 16.46  0    manual    4    4
Mazda RX4 Wag     21.0   6  160 110 3.90 2.875 17.02  0    manual    4    4
Datsun 710        22.8   4  108  93 3.85 2.320 18.61  1    manual    4    1
Hornet 4 Drive    21.4   6  258 110 3.08 3.215 19.44  1 automatic    3    1
Hornet Sportabout 18.7   8  360 175 3.15 3.440 17.02  0 automatic    3    2
Valiant           18.1   6  225 105 2.76 3.460 20.22  1 automatic    3    1
y <- mtcars[, 1] # mileage per gallon 
x <- mtcars[, -1] # all other variables treated as predictors
x <- data.matrix(x, "matrix")
set.seed(123)
trainIdx <- sample(1:nrow(mtcars), round(0.7 * nrow(mtcars)))
fit <- glmnet(x[trainIdx, ], y[trainIdx])
print(fit)

Call:  glmnet(x = x[trainIdx, ], y = y[trainIdx]) 

      Df   %Dev   Lambda
 [1,]  0 0.0000 4.679000
 [2,]  1 0.1383 4.264000
 [3,]  2 0.2626 3.885000
 [4,]  2 0.3700 3.540000
 [5,]  2 0.4593 3.225000
 [6,]  2 0.5333 2.939000
 [7,]  2 0.5948 2.678000
 [8,]  2 0.6459 2.440000
 [9,]  2 0.6883 2.223000
[10,]  2 0.7235 2.026000
[11,]  2 0.7527 1.846000
[12,]  2 0.7770 1.682000
[13,]  3 0.7993 1.532000
[14,]  3 0.8179 1.396000
[15,]  3 0.8335 1.272000
[16,]  3 0.8463 1.159000
[17,]  3 0.8570 1.056000
[18,]  3 0.8659 0.962300
[19,]  3 0.8733 0.876800
[20,]  4 0.8797 0.798900
[21,]  4 0.8862 0.727900
[22,]  4 0.8915 0.663300
[23,]  4 0.8960 0.604300
[24,]  4 0.8997 0.550700
[25,]  4 0.9028 0.501700
[26,]  4 0.9054 0.457200
[27,]  4 0.9075 0.416600
[28,]  4 0.9093 0.379500
[29,]  5 0.9108 0.345800
[30,]  6 0.9124 0.315100
[31,]  5 0.9139 0.287100
[32,]  5 0.9152 0.261600
[33,]  5 0.9162 0.238400
[34,]  5 0.9171 0.217200
[35,]  5 0.9178 0.197900
[36,]  5 0.9184 0.180300
[37,]  5 0.9189 0.164300
[38,]  5 0.9193 0.149700
[39,]  4 0.9197 0.136400
[40,]  4 0.9199 0.124300
[41,]  4 0.9201 0.113200
[42,]  4 0.9203 0.103200
[43,]  5 0.9215 0.094020
[44,]  7 0.9263 0.085660
[45,]  7 0.9313 0.078050
[46,]  6 0.9350 0.071120
[47,]  6 0.9361 0.064800
[48,]  6 0.9371 0.059050
[49,]  7 0.9379 0.053800
[50,]  7 0.9387 0.049020
[51,]  8 0.9396 0.044670
[52,]  9 0.9414 0.040700
[53,] 10 0.9443 0.037080
[54,] 10 0.9473 0.033790
[55,] 10 0.9499 0.030790
[56,] 10 0.9520 0.028050
[57,] 10 0.9538 0.025560
[58,] 10 0.9553 0.023290
[59,] 10 0.9565 0.021220
[60,] 10 0.9575 0.019330
[61,] 10 0.9584 0.017620
[62,] 10 0.9591 0.016050
[63,] 10 0.9597 0.014630
[64,] 10 0.9602 0.013330
[65,] 10 0.9606 0.012140
[66,] 10 0.9609 0.011060
[67,] 10 0.9612 0.010080
[68,] 10 0.9614 0.009186
[69,] 10 0.9616 0.008369
[70,] 10 0.9618 0.007626
[71,] 10 0.9619 0.006949
[72,] 10 0.9620 0.006331
[73,] 10 0.9621 0.005769
[74,] 10 0.9622 0.005256
[75,] 10 0.9623 0.004789
[76,] 10 0.9623 0.004364
[77,] 10 0.9624 0.003976
[78,] 10 0.9624 0.003623
[79,] 10 0.9625 0.003301
[80,] 10 0.9625 0.003008
[81,] 10 0.9625 0.002741
[82,] 10 0.9625 0.002497
[83,] 10 0.9626 0.002275
[84,] 10 0.9626 0.002073
[85,] 10 0.9626 0.001889
[86,] 10 0.9626 0.001721
[87,] 10 0.9626 0.001568
  • glmnet() compute the Lasso regression for a sequence of different tuning parameters.
  • Thus, each of the rows of the table above corresponds to a particular \(\lambda\) in the sequence.

In the above table column Df denotes the number of non-zero coefficients (degrees of freedom), %Dev is the percentage variance explained, and Lambda is the value of the currently chosen tuning parameter.

plot(fit, label = TRUE) 
# label = TRUE makes the plot annotate the curves with the corresponding coeffients labels.

  • each of the curves above corresponds to a variable. It shows that path of a specific coefficient as the value of the tuning parameter changes, and the \(L_1\) norm of the whole coefficient vector increases.
  • the tuning parameter decreases from left to right, that is with a small \(\lambda\) (right) we have more non-zero coefficients.
  • the y-axis corresponds the value of the coefficient.
  • the x-axis is related to the \(L_1\) norm as noted, but is scaled to indicate the number of non-zero coefficients for the current choice of \(\lambda\), which is equal to the effective degrees of freedom (df) for the Lasso.

The computed Lasso coefficient for a particular choice of \(\lambda\) can be printed using:

coef(fit, s = 1)
11 x 1 sparse Matrix of class "dgCMatrix"
                       1
(Intercept) 34.877093111
cyl         -0.867649618
disp         .          
hp          -0.005778702
drat         .          
wt          -2.757808266
qsec         .          
vs           .          
am           .          
gear         .          
carb         .          

Similarly to the case with lm(), we can use the function predict() to predict the outcome from the existing or new input data. We have to however specify the choice of the tuning parameter by setting the value of the argument s.

predict(fit, newx = x[-trainIdx, ], s = c(0.5, 1.5, 2))
                          1        2        3
Datsun 710         25.36098 23.87240 23.22262
Valiant            19.82245 19.42427 19.41920
Duster 360         16.19324 17.27111 17.74858
Merc 230           22.62471 21.86937 21.50396
Merc 450SE         15.20595 16.16123 16.71324
Cadillac Fleetwood 11.25687 13.28117 14.26985
Chrysler Imperial  10.81730 13.01570 14.07314
Fiat 128           25.88928 24.20103 23.47110
Toyota Corolla     27.01880 25.08206 24.22690
Toyota Corona      24.89106 23.51713 22.92237

Each of the columns corresponds to corresponding choice of \(\lambda\).

The choice of \(\lambda\) can be made using cross-validation. We can us the function cv.glmnet() to perform a k-fold cross validation.

In k-fold cross-validation, the original sample is randomly partitioned into k equal sized subsamples. Of the k subsamples, a single subsample is retained as the validation data for testing the model, and the remaining k − 1 subsamples are used as training data.1

set.seed(1)
cvfit <- cv.glmnet(x[trainIdx, ], y[trainIdx], nfolds = 5)

nfolds argument sets the number of folds (k).

plot(cvfit)

The above plot shows the average MSE (red dots) over the folds, together with the standard deviation bounds (error bars) for the \(\lambda\) sequence. The two chosen \(\lambda\) values are indicated with dotted black lines.

The first one:

cvfit$lambda.min
[1] 0.2171905

is the value of \(\lambda\) that gives a minimum mean cross-validated error, and the second:

cvfit$lambda.1se
[1] 0.6632685

gives the biggest \(\lambda\) such that the MSE is within one standard error of the minimum error.

Exercise I

In this exercise you will perform Lasso regression yourself. We will use the Boston dataset from the MASS package. The dataset contains information on the Boston suburbs housing market collected by David Harrison in 1978.

We will try to predict the median value of of homes in the region based on its attributes recorded in other variables.

library(MASS)
?Boston
head(Boston)
     crim zn indus chas   nox    rm  age    dis rad tax ptratio  black lstat medv
1 0.00632 18  2.31    0 0.538 6.575 65.2 4.0900   1 296    15.3 396.90  4.98 24.0
2 0.02731  0  7.07    0 0.469 6.421 78.9 4.9671   2 242    17.8 396.90  9.14 21.6
3 0.02729  0  7.07    0 0.469 7.185 61.1 4.9671   2 242    17.8 392.83  4.03 34.7
4 0.03237  0  2.18    0 0.458 6.998 45.8 6.0622   3 222    18.7 394.63  2.94 33.4
5 0.06905  0  2.18    0 0.458 7.147 54.2 6.0622   3 222    18.7 396.90  5.33 36.2
6 0.02985  0  2.18    0 0.458 6.430 58.7 6.0622   3 222    18.7 394.12  5.21 28.7
dim(Boston)
[1] 506  14
set.seed(123)
trainIdx <- sample(1:nrow(Boston), round(0.7 * nrow(Boston)))
boston.test <- Boston[-trainIdx,"medv"]

Perform a Lasso regression with glmnet. Steps:

  1. Extract the input and output data from the Boston data.frame and convert them if necessary to a correct format.
  2. Use cross-validation to select the value for \(\lambda\).
  3. Inspect the coefficients computed.
  4. Compute the predictions for the test dataset. Evaluate the MSE.
# (... ?)

Classification

Logistic Regression

  • Despite its name, logistic regression is used for classification problems.

  • It performs binary classification (only two categories),

  • The name regression is due to the fact that we are still fitting a function to the data. However, in this case, we are interested in the relationship between the input and the probability that the output is in one of the two classes and not the class assigmnent itself. This function used to model the relationship is called a logit function:

\[P[y = 1 | x] = {\exp^{\beta_0 + \beta_1 x} \over 1 + \exp^{\beta_0 + \beta_1 x}}\]

Logistic Regression Example

We go back to the mtcars dataset.

head(mtcars)
                   mpg cyl disp  hp drat    wt  qsec vs        am gear carb
Mazda RX4         21.0   6  160 110 3.90 2.620 16.46  0    manual    4    4
Mazda RX4 Wag     21.0   6  160 110 3.90 2.875 17.02  0    manual    4    4
Datsun 710        22.8   4  108  93 3.85 2.320 18.61  1    manual    4    1
Hornet 4 Drive    21.4   6  258 110 3.08 3.215 19.44  1 automatic    3    1
Hornet Sportabout 18.7   8  360 175 3.15 3.440 17.02  0 automatic    3    2
Valiant           18.1   6  225 105 2.76 3.460 20.22  1 automatic    3    1

Using logistic regression we will try to predict whether a car had manial or automatic transmission base on its other characteristics.

In R the function glm() can be used to perform logistic regression (as well as mamy other generalized linear models which you can look up by calling ?glm)

Note that currently the column am in mtcars is a numerical variable. However, its values are only 0 or 1 denoting automatic or manual transmission respectively.

class(mtcars$am)
[1] "factor"
table(mtcars$am)

automatic    manual 
       19        13 

We need to convert that column to a factor format, so that R knows the am variable is a categorical one:

mtcars$am <- factor(mtcars$am)

Then we fit the logistic regression predicating the transmission of the car from its mileage per hour (mpg) and the gross horesepower (hp) with the following function call:

fit.logit <- glm(am ~ mpg + hp, data = mtcars, family = "binomial") 

Note that the formula am ~ . means we are interested in explaining ~ the variable am with mpg and hp. You need to set the family to family = "binomial" to indicate you would like to perform a logistic regression. More on this family parameter, which describes the error distribution and the link function can be found by calling ?family.

The model summary can be printed with:

summary(fit.logit)

Call:
glm(formula = am ~ mpg + hp, family = "binomial", data = mtcars)

Deviance Residuals: 
     Min        1Q    Median        3Q       Max  
-1.41460  -0.42809  -0.07021   0.16041   1.66500  

Coefficients:
             Estimate Std. Error z value Pr(>|z|)  
(Intercept) -33.60517   15.07672  -2.229   0.0258 *
mpg           1.25961    0.56747   2.220   0.0264 *
hp            0.05504    0.02692   2.045   0.0409 *
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

(Dispersion parameter for binomial family taken to be 1)

    Null deviance: 43.230  on 31  degrees of freedom
Residual deviance: 19.233  on 29  degrees of freedom
AIC: 25.233

Number of Fisher Scoring iterations: 7

As we see the output is simmilar to the one for the linear model, including the function call, information on residuals, coefficient matrix etc.

Predictions can be computed again using predict() function, with the argument type = "response".

(newcars <- data.frame(mpg = mean(mtcars$mpg),
                      hp = c(110, 170, 155)))
       mpg  hp
1 20.09062 110
2 20.09062 170
3 20.09062 155
predict(fit.logit, newdata = newcars, type = "response")
         1          2          3 
0.09588369 0.74247121 0.55803325 

In the above the output this the probability of a new car with specified mpg and hp to have a manual transmission (wich corresponds to value of 1 in the factor mtcars$am). Classification can be done by assigning “manual” to all the cars with the probability > 0.5, and “automatic” to the rest.

More on logistic regression in R can be found here

Suport Vector Machines (SVM)

  • The following videos contati a brief explanation of the principle of the SVMs:
  • video
  • lectures by Andrew Ng

Support Vectors

Kernel SVM

SVM Example

We will do a simple example from the ISL computing SVM on a simulated data:

set.seed(1)
x <- matrix(rnorm(20*2), ncol=2)
y <- c(rep(-1,10), rep(1,10))
x[y == 1,] <- x[y == 1, ] + 1
plot(x, col=(3-y))
dat <- data.frame(x = x, y=as.factor(y))
head(dat)
         x.1         x.2  y
1 -0.6264538  0.91897737 -1
2  0.1836433  0.78213630 -1
3 -0.8356286  0.07456498 -1
4  1.5952808 -1.98935170 -1
5  0.3295078  0.61982575 -1
6 -0.8204684 -0.05612874 -1

library(e1071)
svmfit <- svm(y ~ ., data=dat, kernel="linear", cost=10, scale=FALSE)
plot(svmfit, dat)

svmfit$index
[1]  1  2  5  7 14 16 17
summary(svmfit)

Call:
svm(formula = y ~ ., data = dat, kernel = "linear", cost = 10, scale = FALSE)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  linear 
       cost:  10 
      gamma:  0.5 

Number of Support Vectors:  7

 ( 4 3 )


Number of Classes:  2 

Levels: 
 -1 1
svmfit <- svm(y~., data=dat, kernel="linear", cost=0.1,scale=FALSE)
plot(svmfit, dat)
svmfit$index
 [1]  1  2  3  4  5  7  9 10 12 13 14 15 16 17 18 20
set.seed(1)

To find a best choice of the tuning parameter “C” use the tune() function

set.seed(1)
tune.out <- tune(svm,y ~ ., data=dat, kernel="linear",
                 ranges=list(cost=c(0.001, 0.01, 0.1, 1,5,10,100)))
summary(tune.out)

Parameter tuning of ‘svm’:

- sampling method: 10-fold cross validation 

- best parameters:
 cost
  0.1

- best performance: 0.1 

- Detailed performance results:
   cost error dispersion
1 1e-03  0.70  0.4216370
2 1e-02  0.70  0.4216370
3 1e-01  0.10  0.2108185
4 1e+00  0.15  0.2415229
5 5e+00  0.15  0.2415229
6 1e+01  0.15  0.2415229
7 1e+02  0.15  0.2415229
bestmod <- tune.out$best.model
summary(bestmod)

Call:
best.tune(method = svm, train.x = y ~ ., data = dat, ranges = list(cost = c(0.001, 0.01, 0.1, 1, 5, 10, 100)), kernel = "linear")


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  linear 
       cost:  0.1 
      gamma:  0.5 

Number of Support Vectors:  16

 ( 8 8 )


Number of Classes:  2 

Levels: 
 -1 1

We build a new test dataset from a similar model as we did for the train data.

xtest <- matrix(rnorm(20*2), ncol=2)
ytest <- sample(c(-1,1), 20, rep=TRUE)
xtest[ytest==1, ] <- xtest[ytest == 1,] + 1
testdat <- data.frame(x=xtest, y=as.factor(ytest))
plot(xtest, col=(3-ytest))

ypred <- predict(bestmod, testdat)
table(predict = ypred, truth = testdat$y)
       truth
predict -1  1
     -1 11  1
     1   0  8

And for the non-tuned model we have:

svmfit <- svm(y~., data=dat, kernel = "linear", cost=.01, scale = FALSE)
ypred <- predict(svmfit, testdat)
table(predict = ypred, truth = testdat$y)
       truth
predict -1  1
     -1 11  2
     1   0  7

Kernel SVM

Now suppose we have non-linearly separable data:

set.seed(123)
# Generate 200 points
x <- matrix(rnorm(200*2), ncol=2)
x[1:100,] <- x[1:100,]+2
x[101:150,] <- x[101:150,]-2
y <-  c(rep(1,150), rep(2,50))
dat <- data.frame(x = x, y = as.factor(y))
plot(x, col=y)
# Let a random half be a training set
train <- sample(200, 100)

We will use the SVM with a radial kernel. Note that here we can additionally specify the gamma parameter for the radial function:

svmfit <- svm(y~., data=dat[train,], kernel = "radial",  gamma=1, cost=1)
plot(svmfit, dat[train,])

summary(svmfit)

Call:
svm(formula = y ~ ., data = dat[train, ], kernel = "radial", gamma = 1, cost = 1)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  radial 
       cost:  1 
      gamma:  1 

Number of Support Vectors:  35

 ( 19 16 )


Number of Classes:  2 

Levels: 
 1 2
table(true <- dat[-train,"y"], pred=predict(svmfit, newx = dat[-train,]))
   pred
     1  2
  1 58 14
  2 21  7

We can tune both gamma and cost parameters:

set.seed(17)
tune.out <- tune(svm, y~., data=dat[train,], kernel="radial", 
              ranges=list(cost=c(0.1,1,10,100,1000), gamma=c(0.5,1,2,3,4)))
summary(tune.out)

Parameter tuning of ‘svm’:

- sampling method: 10-fold cross validation 

- best parameters:
 cost gamma
   10   0.5

- best performance: 0.08 

- Detailed performance results:
    cost gamma error dispersion
1  1e-01   0.5  0.22 0.15491933
2  1e+00   0.5  0.10 0.06666667
3  1e+01   0.5  0.08 0.09189366
4  1e+02   0.5  0.09 0.08755950
5  1e+03   0.5  0.10 0.11547005
6  1e-01   1.0  0.22 0.15491933
7  1e+00   1.0  0.10 0.06666667
8  1e+01   1.0  0.10 0.10540926
9  1e+02   1.0  0.11 0.09944289
10 1e+03   1.0  0.14 0.13498971
11 1e-01   2.0  0.22 0.15491933
12 1e+00   2.0  0.12 0.09189366
13 1e+01   2.0  0.10 0.10540926
14 1e+02   2.0  0.12 0.10327956
15 1e+03   2.0  0.16 0.13498971
16 1e-01   3.0  0.22 0.15491933
17 1e+00   3.0  0.12 0.10327956
18 1e+01   3.0  0.10 0.08164966
19 1e+02   3.0  0.14 0.10749677
20 1e+03   3.0  0.17 0.14181365
21 1e-01   4.0  0.22 0.15491933
22 1e+00   4.0  0.12 0.10327956
23 1e+01   4.0  0.10 0.09428090
24 1e+02   4.0  0.13 0.11595018
25 1e+03   4.0  0.18 0.13165612
table(true <- dat[-train,"y"], pred=predict(tune.out$best.model,newx=dat[-train,]))
   pred
     1  2
  1 56 16
  2 21  7
plot(tune.out$best.model, dat[train,])

Random Forest

Decision trees

Decision tree on classification of Titanic Survivors:

Source: wiki

Ensamble Methods

ESL

ESL

Source: link

  • Averaging over a collection of decision trees makes the predictions more stable.

  • One of the random forest features which makes it perform well, is the introduction of randomness into the candidate splitting variables, which reduces correlation between the generated trees.

  • What this means is that, at each splitting levels, the pool of the potential splitting variables does not contain all variables, but only a random subset of them.

In R random forest can be computed with the function randomForest() in randomForest package. There are two important parameters for a random forest prediction:

  • mtry – Number of variables randomly sampled as candidates at each split.
  • ntree– Number of trees generated (to be averaged over).

We will use the iris dataset to show how classification can be done with randomForest(). Regression can be done using the same function calls.

Iris is a famous (Fisher’s or Anderson’s) data set gives the measurements in centimeters of the variables sepal length and width and petal length and width, respectively, for 50 flowers from each of 3 species of iris. The species are Iris setosa, versicolor, and virginica.

## Classification:
data(iris)
# set seed for reproducibility since random forest is a random predictor 
set.seed(71) 
iris.rf <- randomForest(Species ~ ., data=iris, importance=TRUE,
                        proximity=TRUE)
print(iris.rf)

Call:
 randomForest(formula = Species ~ ., data = iris, importance = TRUE,      proximity = TRUE) 
               Type of random forest: classification
                     Number of trees: 500
No. of variables tried at each split: 2

        OOB estimate of  error rate: 5.33%
Confusion matrix:
           setosa versicolor virginica class.error
setosa         50          0         0        0.00
versicolor      0         46         4        0.08
virginica       0          4        46        0.08
## Look at variable importance:
round(importance(iris.rf), 2)
             setosa versicolor virginica MeanDecreaseAccuracy MeanDecreaseGini
Sepal.Length   6.04       7.85      7.93                11.51             8.77
Sepal.Width    4.40       1.03      5.44                 5.40             2.19
Petal.Length  21.76      31.33     29.64                32.94            42.54
Petal.Width   22.84      32.67     31.68                34.50            45.77

Exercise II

Using random forest regression, predict the housing prices in the Boston dataset used previously for the exercise on the Lasso regression.

  1. First the random forest model with default parameters
  2. Compute the MSE for the model and compare with the one from Lasso regression.
  3. Plot the predicted values and the true median house values for the test data.
  4. Plot and inspect the variable importance. Do they agree with the coefficients found in Lasso regression?
data(Boston)
set.seed(123)
trainIdx <- sample(1:nrow(Boston), round(0.7 * nrow(Boston)))
head(Boston)
     crim zn indus chas   nox    rm  age    dis rad tax ptratio  black lstat medv
1 0.00632 18  2.31    0 0.538 6.575 65.2 4.0900   1 296    15.3 396.90  4.98 24.0
2 0.02731  0  7.07    0 0.469 6.421 78.9 4.9671   2 242    17.8 396.90  9.14 21.6
3 0.02729  0  7.07    0 0.469 7.185 61.1 4.9671   2 242    17.8 392.83  4.03 34.7
4 0.03237  0  2.18    0 0.458 6.998 45.8 6.0622   3 222    18.7 394.63  2.94 33.4
5 0.06905  0  2.18    0 0.458 7.147 54.2 6.0622   3 222    18.7 396.90  5.33 36.2
6 0.02985  0  2.18    0 0.458 6.430 58.7 6.0622   3 222    18.7 394.12  5.21 28.7
# (...?)

Dimensional Reduction

Principal Component Analysis (PCA)

An example from ESL Chapter 14:

PCA Example: US crime rates

Now we will do an example using the built in dataset on violent crime rates in the US from 1975.

The code is adapted from ISL.

?USArrests
head(USArrests)
           Murder Assault UrbanPop Rape
Alabama      13.2     236       58 21.2
Alaska       10.0     263       48 44.5
Arizona       8.1     294       80 31.0
Arkansas      8.8     190       50 19.5
California    9.0     276       91 40.6
Colorado      7.9     204       78 38.7
states <- row.names(USArrests)

Mean and variance of the crime rates across all states:

apply(USArrests, 2, mean)
  Murder  Assault UrbanPop     Rape 
   7.788  170.760   65.540   21.232 
apply(USArrests, 2, var)
    Murder    Assault   UrbanPop       Rape 
  18.97047 6945.16571  209.51878   87.72916 

Compute a PCA:

In R you can use the function prcomp() to do PCA. Check the help page ?prcomp for details.

The calculation is done by a singular value decomposition of the (centered and possibly scaled) data matrix, not by using eigen on the covariance matrix. This is generally the preferred method for numerical accuracy. The print method for these objects prints the results in a nice format and the plot method produces a scree plot.

prcomp() is a preferred method over princomp.

pr.out <- prcomp(USArrests, scale=TRUE)
names(pr.out)
[1] "sdev"     "rotation" "center"   "scale"    "x"       
pr.out$center
  Murder  Assault UrbanPop     Rape 
   7.788  170.760   65.540   21.232 
pr.out$scale
   Murder   Assault  UrbanPop      Rape 
 4.355510 83.337661 14.474763  9.366385 
pr.out$rotation
                PC1        PC2        PC3         PC4
Murder   -0.5358995  0.4181809 -0.3412327  0.64922780
Assault  -0.5831836  0.1879856 -0.2681484 -0.74340748
UrbanPop -0.2781909 -0.8728062 -0.3780158  0.13387773
Rape     -0.5434321 -0.1673186  0.8177779  0.08902432
dim(pr.out$x)
[1] 50  4

The output of prcomp() is a list containing the following:

  • sdev: the standard deviations of the principal components (i.e., the square roots of the eigenvalues of the co-variance/correlation matrix, X^TX)
  • rotation: the matrix of variable loadings (i.e., a matrix whose columns contain the eigenvectors).
  • x: the value of the rotated data (the centered (and scaled if requested) data multiplied by the rotation matrix) is returned.
  • center, scale the centering and scaling used, or FALSE

Each principal component loading and score vector is unique, up to a sign flip

biplot(pr.out, scale=0, cex = 0.8)

Each principal component loading and score vector is unique, up to a sign flip So another software of R package could e.g. return this plot instead:

pr.out$rotation=-pr.out$rotation
pr.out$x=-pr.out$x
biplot(pr.out, scale=0, cex = 0.8)

  • the first loading vector places approx. equal weight on Assault, Murder, and Rape, with much less weight on UrbanPop. Hence this component roughly corresponds to a measure of overall rates of serious crimes.
  • The second loading vector places most of its weight on UrbanPop. Hence, it roughly corresponds to the level of urbanization of the state.
  • The crime-related variables are located close to each other, and that UrbanPop is far from them.
  • The crime-related variables are correlated with each other, and that the UrbanPop variable is less correlated with the other three.

A scree plot

Choose the smallest number of principal components that are required in order to explain a sizable amount of the variation in the data.

Look for a point at which the proportion of variance explained by each subsequent principal component drops off. This is often referred to as an elbow in the scree plot

pr.out$sdev
[1] 1.5748783 0.9948694 0.5971291 0.4164494
pr.var <- pr.out$sdev^2
pr.var
[1] 2.4802416 0.9897652 0.3565632 0.1734301
pve <- pr.var/sum(pr.var)
pve
[1] 0.62006039 0.24744129 0.08914080 0.04335752
plot(pve, xlab="Principal Component", ylab="Proportion of Variance Explained", ylim=c(0,1),type='b')

Multidimensional Scaling (MDS)

MDS algorithm aims to place each object in N-dimensional space such that the between-object distances are preserved as well as possible. Each object is then assigned coordinates in each of the N dimensions. The number of dimensions of an MDS plot N can exceed 2 and is specified a priori. Choosing N=2 optimizes the object locations for a two-dimensional scatterplot.

There are different types of MDS methods including, Classical MDS, Metric MDS and Non-metric MDS. The details on the differences ca be found on:

MDS Example: Color perception

Ekman studied how people perceive colors. He collected data where 31 subjects rated the similarity pf each pair of 14 colors on a a 5-point scale (0 = no similarity, 4 = identical). After averaging the 21 similarities ratings were divided by 4 to transform them into a unit interval. The 14 colors studied had wavelengths between 434 and 674 nm.

ekmanSim <- readRDS("./data/ekman.rds")
# convert similarities to dissimilarities
ekmanDist <- 1- ekmanSim
wavelengths <- round(seq( 434, 674, length.out = 14))

Use cmdscale() built-in function for classical MDS. Metric iterative MDS and non-metric MDS function are available in a package smacof and other packages are also compared here.

ekmanMDS <- cmdscale(ekmanDist, k = 2)
res <- data.frame(ekmanMDS)
res$wavelength <- factor(wavelengths, levels = wavelengths)
ggplot(res, aes(X1, X2)) + geom_point() + theme_bw() +
  geom_text(aes(label = wavelength), hjust=0.5, vjust=-1, size = 3)

I mapped the wavelengths to hexadecimal colors using this website.

colorsDF <- data.frame(
  wavelength = wavelengths,
  hex = c("#2800ff", "#0051ff", "#00aeff", "#00fbff", "#00ff28", "#4eff00",
          "#92ff00", "#ccff00", "#fff900", "#ffbe00", "#ff7b00", "#ff3000",
          "#ff0000", "#ff0000"))
ggplot(res, aes(X1, X2)) + 
  geom_point(aes(color = wavelength), size = 2) + theme_bw() +
  geom_text(aes(label = wavelength), hjust=0.5, vjust=-1, size = 3) +
  scale_color_manual(values = as.character(colorsDF$hex))

MDS reproduces the recognizable 2D color wheel

t-Distributed Stochastic Neighbor Embedding (tSNE)

What is tSNE?

  • a technique for dimensionality reduction that is particularly well suited for the visualization of high-dimensional datasets.2
  • the method was first introduced by L.J.P. van der Maaten in 2008. The original paper is available here
  • t-SNE tries to group local data points closer to each other, instead of trying to preserve the global structure like many dimensionality reduction techniques.

tSNE Example: Mass cytometry

The following example shows how to calculate and plot a 2D t-SNE projection using the Barnes-Hut-SNE algorithm, using the Rtsne package for R. This example was worked out by Lukas Weber.

  • The dataset used is the mass cytometry of healthy human bone marrow data set “Marrow1”, seen in Figure 1b of Amir et al. (2013).
  • Mass cytometry is a recent advance in flow cytometry, which allows expression levels of up to 40 proteins per cell to be measured in hundreds of cells per second.3
  • This dataset provides an example of an ideal t-SNE projection, where cells from different cell populations (types) are grouped as distinct clusters of points in the 2-dimensional projection, and there is clear visual separation between clusters.

Source code: github link

# Skip the block above if it takes too long to load.
# The subsetted data has beed porvided in a smaller file
dat <- read.csv("./data/healthyHumanBoneMarrow_small.csv")
dim(dat)
[1] 1000   36
dat[1:10, 1:6]
   Event.    Time Cell.Length  X191.DNA  X193.DNA X115.CD45
1  100704  261232    36.35262 1052.8925 2184.2791 606.56268
2    9863   24602    25.07553  697.9535 1158.0222 192.41901
3  466415 1084484    34.44039  409.5371  542.7836  98.22443
4  216327  623282    43.57069  998.1034 1990.9073 482.09525
5  227911  925587    48.47278  697.8970 1274.9041 212.06926
6  328317  900941    29.00149  921.0044 1923.2419 284.07599
7  295168  732036    21.45761  563.6906 1198.7548  22.76224
8  198694  522453    52.10402  425.8115  657.4357 137.40990
9  106346  179388    22.12231 1106.9290 1953.5457  32.46744
10 413740  910973    27.23294  481.7126 1139.8833 209.80591
# select 13 protein markers to use in calculation of t-SNE projection
# CD11b, CD123, CD19, CD20, CD3, CD33, CD34, CD38, CD4, CD45, CD45RA, CD8, CD90
# (see Amir et al. 2013, Supplementary Tables 1 and 2)
colnames_proj <- colnames(dat)[c(11, 23, 10, 16, 7, 22, 14, 28, 12, 6, 8, 13, 30)]
colnames_proj  # check carefully!
 [1] "X144.CD11b"           "X160.CD123"           "X142.CD19"            "X147.CD20"            "X110.111.112.114.CD3" "X158.CD33"           
 [7] "X148.CD34"            "X167.CD38"            "X145.CD4"             "X115.CD45"            "X139.CD45RA"          "X146.CD8"            
[13] "X170.CD90"           
# arcsinh transformation
# (see Amir et al. 2013, Online Methods, "Processing of mass cytometry data")
asinh_scale <- 5
dat <- asinh(dat / asinh_scale)  # transforms all columns! including event number etc
# prepare data for Rtsne
dat <- dat[, colnames_proj]      # select columns to use
dat <- dat[!duplicated(dat), ]  # remove rows containing duplicate values within rounding
dim(dat)
[1] 999  13
library(Rtsne)
# run Rtsne (Barnes-Hut-SNE algorithm)
# without PCA step (see Amir et al. 2013, Online Methods, "viSNE analysis")
set.seed(123)  # set random seed
rtsne_out <- Rtsne(as.matrix(dat), pca = FALSE, verbose = TRUE)
Read the 999 x 13 data matrix successfully!
Using no_dims = 2, perplexity = 30.000000, and theta = 0.500000
Computing input similarities...
Normalizing input...
Building tree...
 - point 0 of 999
Done in 0.13 seconds (sparsity = 0.116284)!
Learning embedding...
Iteration 50: error is 69.448402 (50 iterations in 0.64 seconds)
Iteration 100: error is 60.170135 (50 iterations in 0.52 seconds)
Iteration 150: error is 59.830064 (50 iterations in 0.52 seconds)
Iteration 200: error is 59.790362 (50 iterations in 0.53 seconds)
Iteration 250: error is 2.494854 (50 iterations in 0.50 seconds)
Iteration 300: error is 1.072682 (50 iterations in 0.48 seconds)
Iteration 350: error is 0.932446 (50 iterations in 0.48 seconds)
Iteration 400: error is 0.893893 (50 iterations in 0.53 seconds)
Iteration 450: error is 0.878459 (50 iterations in 0.51 seconds)
Iteration 500: error is 0.865561 (50 iterations in 0.49 seconds)
Iteration 550: error is 0.856887 (50 iterations in 0.50 seconds)
Iteration 600: error is 0.852200 (50 iterations in 0.50 seconds)
Iteration 650: error is 0.847460 (50 iterations in 0.49 seconds)
Iteration 700: error is 0.844339 (50 iterations in 0.50 seconds)
Iteration 750: error is 0.841766 (50 iterations in 0.49 seconds)
Iteration 800: error is 0.838928 (50 iterations in 0.52 seconds)
Iteration 850: error is 0.837514 (50 iterations in 0.49 seconds)
Iteration 900: error is 0.835641 (50 iterations in 0.48 seconds)
Iteration 950: error is 0.835091 (50 iterations in 0.54 seconds)
Iteration 999: error is 0.834370 (50 iterations in 0.51 seconds)
Fitting performed in 10.21 seconds.
# plot 2D t-SNE projection
plot(rtsne_out$Y, asp = 1, pch = 20, col = "blue", 
     cex = 0.75, cex.axis = 1.25, cex.lab = 1.25, cex.main = 1.5, 
     xlab = "t-SNE dimension 1", ylab = "t-SNE dimension 2", 
     main = "2D t-SNE projection")

Exercise III

Download MNIST data of the digits images from the Kaggle competition. The code is adapted from the one here.

The ./data/train.csv and ./data/test.csv files are data on the 28x28 pixel images of digits (0-9). The data is composed of:

# Skip the previous block and load the already subsetted training data (faster).
train <- read.csv("./data/train_small.csv")
dim(train)
[1] 1000  786
  1. Compute tSNE embedding of the training data.
  2. Visualized the tSNE 2D projection with the digit labels and coloring.
  3. Perform a principal component analysis on the training data.
  4. Plot the sample the PCA scores with the digit labels and coloring.
# (... ?)

What do you observe? How does tSNE compare with PCA in this case?

Cluster Analysis

Check out clustering methods available on CRAN.

k-means

  • k-means is a simple iterative relocation method for clustering data into \(k\) distinct non-overlapping groups.
  • The algorithm minimizes the variation within each cluster.

Demonstration of how k-means clustering works can be found in this animation

Drawbacks:

  • The number clusters \(k\) must be specified before clustering.
  • Each time the algorithm is run, the centers of the clusters are randomly initialized leading to different final cluster assignments.

The choice of the number of clusters, \(k\) can be made by considering statistics such as:

  • Gap Statistic link
  • Silhouette statistic link
  • Calinski-Harbasz index link

k-means for image segmentation/compression

One of the application of k-means clustering is image segmentation. The code provided are adapted from the found here.

Download and read the image

Download your favorite image / do a quick Google search for one / use the one provided. Make sure that your picture is not too big (e.g. around is fine 400 x 600 px). Otherwise, the code might take a while to run.

The image provided is a picture of colorful tulips in the Netherlands downloaded from here.

library(jpeg)
url <- "http://www.infohostels.com/immagini/news/2179.jpg"
# Download the file and save it as "Image.jpg" in the directory
dFile <- download.file(url, "./figures/Image.jpg")
trying URL 'http://www.infohostels.com/immagini/news/2179.jpg'
Content type 'image/jpeg' length 174940 bytes (170 KB)
==================================================
downloaded 170 KB
img <- readJPEG("./figures/Image.jpg") # Read the image
(imgDm <- dim(img))
[1] 480 960   3

Vectorize the data into RGB channels

Represent the 3D array as a data frame with each row representing a single pixel. The columns x and y give the pixel location, and R, G, B denote the pixel intensity in red, green, blue respectively.

# Assign RGB channels to data frame
imgRGB <- data.frame(
  x = rep(1:imgDm[2], each = imgDm[1]),
  y = rep(imgDm[1]:1, imgDm[2]),
  R = as.vector(img[,,1]),
  G = as.vector(img[,,2]),
  B = as.vector(img[,,3])
  )

Plot the image

# ggplot theme to be used
plotTheme <- function() {
  theme(
    panel.background = element_rect(
      size = 3,
      colour = "black",
      fill = "white"),
    axis.ticks = element_line(
      size = 2),
    panel.grid.major = element_line(
      colour = "gray80",
      linetype = "dotted"),
    panel.grid.minor = element_line(
      colour = "gray90",
      linetype = "dashed"),
    axis.title.x = element_text(
      size = rel(1.2),
      face = "bold"),
    axis.title.y = element_text(
      size = rel(1.2),
      face = "bold"),
    plot.title = element_text(
      size = 20,
      face = "bold",
      vjust = 1.5)
  )
}
# Plot the image
ggplot(data = imgRGB, aes(x = x, y = y)) + 
  geom_point(colour = rgb(imgRGB[c("R", "G", "B")])) +
  labs(title = "Original Image: Colorful Flowers") +
  xlab("x") +
  ylab("y") +
  plotTheme()

k-means in R

Choose the number of clusters (colors in this case) and do k-means clustering with kmeans() built-in function.

kClusters <- 2
kMeans <- kmeans(imgRGB[, c("R", "G", "B")], centers = kClusters)
kColours <- rgb(kMeans$centers[kMeans$cluster,])

Then plot the results.

ggplot(data = imgRGB, aes(x = x, y = y)) + 
  geom_point(colour = kColours) +
  labs(title = paste("k-Means Clustering of", kClusters, "Colours")) +
  xlab("x") +
  ylab("y") + 
  plotTheme()

kClusters <- 6
kMeans <- kmeans(imgRGB[, c("R", "G", "B")], centers = kClusters)
names(kMeans)
[1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss" "betweenss"    "size"         "iter"         "ifault"      
kColours <- rgb(kMeans$centers[kMeans$cluster,])

Then plot the results.

ggplot(data = imgRGB, aes(x = x, y = y)) + 
  geom_point(colour = kColours) +
  labs(title = paste("k-Means Clustering of", kClusters, "Colours")) +
  xlab("x") +
  ylab("y") + 
  plotTheme()

Hierarchical clustering

Alexander Calder’s mobile

Alexander Calder’s mobile

If you don’t want to specify or if it is hard to choose the number of clusters based on the diagnostics you can try hierarchical clustering, which provides a graphical tree-based representation of the data, called a dendogram, that would allow you to evaluate where the cutoff for grouping should occur.

The hierarchical clustering algorithm summary is given below

Source: ISL

The results for hierarchical clustering will differ based on your choice of:

  • the distance measure between a pair of observations:
    • Euclidean,
    • Manhattan,
    • Jaccard
    • etc. link
  • the dissimilarity between 2 clusters, i.e. the criteria that is used for grouping clusters that have been composed:

Hierarchical Clustering Example: Iris dataset

Again, we will use the Fisher’s Iris dataset used before in the random forest section. We will show that using hierarchical clustering of the observed attributes one can cluster flowers into groups corresponding to their species.

?iris
head(iris)
  Sepal.Length Sepal.Width Petal.Length Petal.Width Species
1          5.1         3.5          1.4         0.2  setosa
2          4.9         3.0          1.4         0.2  setosa
3          4.7         3.2          1.3         0.2  setosa
4          4.6         3.1          1.5         0.2  setosa
5          5.0         3.6          1.4         0.2  setosa
6          5.4         3.9          1.7         0.4  setosa

We will use the built-in function hclust() to perform hierarchical clustering. Only the data on the petal dimensions will be used for computing the distances between flower.

?hclust
# We use the Euclidean distance for the dissimilarities between flowers
distMat <- dist(iris[, 3:4])
# We use the "complete" linkage method for computing the cluster distances.
clusters <- hclust(distMat, method = "complete")
plot(clusters)

Inspecting the plot we see that a reasonable choice of the number of clusters is either 3 or 4.

plot(clusters)
abline(a = 2, b = 0, col = "blue")
abline(a = 3, b = 0, col = "blue")

Let’s pick 3 clusters. To get the leaves/observations (flowers in this case) assignments using only 3 clusters from the chopped tree we can use a cutree() function.

(clusterCut <- cutree(clusters, 3))
  [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 3 2 2 2 3 2 3 3 3 3 2 3 3 2 3 2 3 2 3 2
 [74] 2 3 3 2 2 2 3 3 3 3 2 2 2 2 3 3 3 3 2 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[147] 2 2 2 2
table(clusterCut, iris$Species)
          
clusterCut setosa versicolor virginica
         1     50          0         0
         2      0         21        50
         3      0         29         0

From the table we see that the sentosa and virginica were correctly assigned to separate groups. However, the method had problems to group the versicolor flowers into a separate cluster.

We can try another linkage method like “average” and see if we perform better.

?hclust
# We use the Euclidean distance for the dissimilarities between flowers
distMat <- dist(iris[, 3:4])
# We use the "complete" linkage method for computing the cluster distances.
clusters <- hclust(distMat, method = "average")
plot(clusters)

Here we can choose 3 or 5 clusters:

plot(clusters)
abline(a = 1.4, b = 0, col = "blue")
abline(a = 0.8, b = 0, col = "blue")

Again we choose 3 clusters

clusterCut <- cutree(clusters, 3)
table(clusterCut, iris$Species)
          
clusterCut setosa versicolor virginica
         1     50          0         0
         2      0         45         1
         3      0          5        49

We see that this time we do a little better in clustering the versicolors together.

We now plot the flowers using petal dimensions as coordinates, and show their cluster assignment as well as color points by species.

ggplot(iris, aes(Petal.Length, Petal.Width)) + theme_bw() +
  geom_text(aes(label = clusterCut), vjust = -1) + 
  geom_point(aes(color = Species))


  1. https://en.wikipedia.org/wiki/Cross-validation_(statistics)#k-fold_cross-validation

  2. https://lvdmaaten.github.io/tsne/

  3. https://github.com/lmweber/Rtsne-example

LS0tCnRpdGxlOiAiU3RhdGlzdGljYWwgTWV0aG9kcyB3aXRoIFIiCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCiMgUmVsZXZhbnQgQm9va3MKCkZvciBtb3JlIGJhY2tncm91bmQgaW4gc3RhdGlzdGljcyBjaGVjayBvdXQgdGhlIGZvbGxvd2luZyBib29rczoKCiogWyJBbiBpbnRyb2R1Y3Rpb24gdG8gU3RhdGlzdGljYWwgTGVhcm5pbmciXShodHRwOi8vd3d3LWJjZi51c2MuZWR1L35nYXJldGgvSVNML2dldGJvb2suaHRtbCkgW0VTTF0gYnkgSmFtZXMsIFdpdHRlbiwgSGFzdGllIGFuZCBUaWJzaGlyYW5pCiogWyJFbGVtZW50cyBvZiBzdGF0aXN0aWNhbCBsZWFybmluZyJdKGh0dHA6Ly93d3cuc3ByaW5nZXIuY29tL2dwL2Jvb2svOTc4MDM4Nzg0ODU3MCkgW0lTTF0gYnkgSGFzdGllLCBUaWJzaGlyYW5pIGFuZCBGcmllZG1hbiAKKiBbIkludHJvZHVjdGlvbiB0byBMaW5lYXIgUmVncmVzc2lvbiBBbmFseXNpcyJdKGh0dHA6Ly93d3cud2lsZXkuY29tL1dpbGV5Q0RBL1dpbGV5VGl0bGUvcHJvZHVjdENkLTA0NzA1NDI4MTAuaHRtbCkgYnkgTW9udGdvbWVyeSwgUGVjaywgVmlubmluZwoKQWxsIHByZXNlbnRlZCBtYXRlcmlhbCBpcyB1bmRlciBhIApbQ3JlYXRpdmUgQ29tbW9ucyBBdHRyaWJ1dGlvbi1Ob25Db21tZXJjaWFsLVNoYXJlQWxpa2UgNC4wIEludGVybmF0aW9uYWwgTGljZW5zZV0oaHR0cHM6Ly9jcmVhdGl2ZWNvbW1vbnMub3JnL2xpY2Vuc2VzL2J5LXNhLzQuMC8pLgoKCiMgSW5zdGFsbCBhbmQgbG9hZCBwYWNrYWdlcwoKYGBge3IgY2hlY2staW5zdGFsbC1sb2FkLXBhY2thZ2VzLCB3YXJuaW5nPUZBTFNFLCBtZXNzYWdlPUZBTFNFfQojIENsZWFyIHRoZSB3b3Jrc3BhY2UKcm0obGlzdCA9IGxzKCkpCgojIExpc3Qgb2YgcGFja2FnZSBuZWVkZWQgZm9yIHRoaXMgd29ya3Nob3AKcmVxcGtnIDwtIGMoImdncGxvdDIiLCJqcGVnIiwgIlJ0c25lIiwgInJhbmRvbUZvcmVzdCIsICJNQVNTIikKCiMgQ2hlY2sgaWYgdGhlIHBhY2thZ2VzIGFyZSBpbnN0YWxsZWQ6CmlucGtnID0gaW5zdGFsbGVkLnBhY2thZ2VzKClbLCAiUGFja2FnZSJdICNpbnN0YWxsZWQgcGFja2FnZXMKbmVlZGVkcGtnID0gcmVxcGtnWyFyZXFwa2cgJWluJSBpbnBrZ10KaWYobGVuZ3RoKG5lZWRlZHBrZykgPiAwKXsKICBzdG9wKHBhc3RlKCJcbiBOZWVkIHRvIGluc3RhbGwgdGhlIGZvbGxvd2luZyBwYWNrYWdlOiIsIG5lZWRlZHBrZykpCn0KYGBgCgpJZiB5b3UgaGF2ZW4ndCBkb25lIHRoYXQgYWxyZWFkeSwgZG93bmxvYWQgdGhlIHdvcmtzaG9wIG1hdGVyaWFsczoKYGBge3IgZXZhbCA9IEZBTFNFfQp1cmxfdG9fY2xhc3NfbWF0ZXJpYWxzIDwtICJodHRwczovL3N0YW5mb3JkLmJveC5jb20vcy9zcW1wamRidXhhMjlhOGZlbm0xY3F4YzByaTZjMzI3NiIKIyBDaGFuZ2UgdGhlIHBhdGggZGlyZWN0b3J5IGFuZCB1bmNvbW1lbnQgdGhlIGxpbmUgYmVsb3cKI3NldHdkKCIvcGF0aC90by9kaXIvIikKZG93bmxvYWQuZmlsZSgidXJsX3RvX2NsYXNzX21hdGVyaWFscyIsICJSX3dvcmtzaG9wLnppcCIpCnVuemlwKCJSX3dvcmtzaG9wLnppcCIpCmBgYAoKCiMgU3RhdGlzdGljYWwgTW9kZWxpbmcKCldoeSBkbyB5b3UgbmVlZCBhIG1vZGVsPyBZb3Ugd291bGQgbGlrZSB0bzoKCiogZGV0ZWN0IHRoZSBwYXR0ZXJuIGluIHRoZSBkYXRhCiogcHJlZGljdCB0aGUgb3V0Y29tZSBmb3IgbmV3IG9ic2VydmF0aW9ucwoqIGFzc2VzcyB0aGUgc2lnbmlmaWNhbmNlIG9mIHNvbWUgZmFjdG9ycyBvbiB0aGUgb3V0Y29tZSBvZiBpbnRlcmVzdAoqIHBlcmZvcm0gc3RhdGlzdGljYWwgdGVzdHMuCgpJbiB0aGlzIHdvcmtzaG9wICoqeW91IHdvbid0IGxlYXJuIG1hdGhlbWF0aWNhbCBkZXRhaWxzKiogYWJvdXQgaG93CnRoZSBtZXRob2RzIHByZXNlbnQgd29yayBvciBob3cgdG8gY3JlYXRlIGEgZ29vZCBzdGF0aXN0aWNhbGx5LXNvdW5kIG1vZGVsLgpJIHdpbGwganVzdCBlcXVpcCB5b3Ugd2l0aCB0aGUga25vd2xlZGdlIG9mIGhvdyB0byB1c2Ugc29tZSBvZiB0aGUgUiBwYWNrYWdlcyAKdGhhdCBpbXBsZW1lbnQgdGhlIG1vcmUgcG9wdWxhciBzdGF0aXN0aWNhbCB0ZWNobmlxdWVzLCBhbmQgaG93IHRvIGludGVycHJldAp0aGVpciBvdXRwdXRzLgoKWW91IGNhbiBjaGVjayBvdXQgb3RoZXIgd29ya3Nob3BzIGUuZiBzdGF0aXN0aWNhbCBsZWFybmluZyBvciBtYWNoaW5lIGxlYXJuaW5nIAp0byBsZWFybiBtb3JlIG9uIHRoZW9yeSB0aGVzZSBtZXRob2RzIGFyZSBiYXNlZCBvbi4KClRvIGlsbHVzdHJhdGUgaG93IHN0YXRpc3RpY2FsIG1vZGVsbGluZyB3b3JrcyBpbiBSIHdlIHdpbGwgdXNlIHRoZSAKYG10Y2Fyc2AsIGJ1aWx0LWluIGRhdGFzZXQsIHRoYXQgY29tZXMgZnJvbSBhIDE5NzQgaXNzdWUgb2YgTW90b3IgVHJlbmRzIAptYWdhemluZS4gCgpgYGB7cn0KZGF0YSgibXRjYXJzIikKaGVhZChtdGNhcnMpCmBgYAoKKiBlYWNoIHJvdyBvZiBgbXRjYXJzYCByZXByZXNlbnRzIG9uZSBtb2RlbCBvZiBjYXIsIGluZGljYXRlZCBpbiB0aGUgcm93LW5hbWVzLiAKKiBlYWNoIGNvbHVtbiBpcyBvbmUgYXR0cmlidXRlIG9mIHRoZSBjYXIsIHN1Y2ggYXMgdGhlIG1pbGVzIHBlciBnYWxsb24gKG9yIGZ1ZWwgZWZmaWNpZW5jeSksIHRoZSBudW1iZXIgb2YgY3lsaW5kZXJzLCB0aGUgZGlzcGxhY2VtZW50IChvciB2b2x1bWUpIG9mIHRoZSAKY2FyJ3MgZW5naW5lIGluIGN1YmljIGluY2hlcywgd2hldGhlciB0aGUgY2FyIGhhcyBhbiBhdXRvbWF0aWMgb3IgbWFudWFsIAp0cmFuc21pc3Npb24uCgojIEh5cG90aGVzaXMgdGVzdGluZwoKT25lIG9mdGVuIGFza2VkIHF1ZXN0aW9uIGluIGRhdGEgYW5hbHlzaXMgaXMgd2hldGhlciB0aGVyZSBpcyAKYSAqKnNpZ25pZmljYW50IGRpZmZlcmVuY2UqKiBiZXR3ZWVuIHR3byBzYW1wbGVzLCBvciBncm91cHMuIEZvciBleGFtcGxlLCBvbmUgCmJlIGludGVyZXN0ZWQgaW4gd2hldGhlciBhIGdyb3VwIG9mIHBhdGllbnRzIHN1YmplY3QgdG8gYSBtZWRpY2FsIHRyZWF0bWVudCAKaGFkIGJldHRlciBvdXRjb21lcyB0aGFuIGEgY29udHJvbCBncm91cC4gVGhlc2Uga2luZHMgb2YgKipoeXBvdGhlc2VzKiogY2FuIGJlCnRlc3RlZCB3aXRoIHN0YXRpc3RpY2FsIHByb2NlZHVyZXMuCgpIZXJlIHdlIHdpbGwgc2hvdyBob3cgdG8gcGVyZm9ybSAqKmEgU3R1ZGVudCdzIFQtdGVzdCoqLCB3aGljaCBpcyBvbmUgb2YgdGhlIAptZXRob2RzIHN0YXRpc3RpY2lhbnMgdHJhZGl0aW9uYWxseSB1c2UgdG8gdGVzdCB0aGUgZXF1YWxpdHkgb2YgdGhlIG1lYW5zCm9mIHR3byBwb3B1bGF0aW9ucy4KCiMjIEh5cG90aGVzaXMgdGVzdDogZXhhbXBsZQoKQW5hbHl6aW5nIG91ciBleGFtcGxlIGRhdGFzZXQgd2UgbWlnaHQgYmUgaW50ZXJlc3RlZCB3aGV0aGVyIHRoZSBmdWVsIGVmZmljaWVuY3ksCmkuZS4gbWlsZWFnZSBwZXIgZ2FsbG9uIGlzIGRpZmZlcmVudCBmb3IgdGhlIGNhcnMgd2l0aCBhdXRvbWF0aWMgYW5kIG1hbnVhbCAKdHJhbnNtaXNzaW9uLiBUaGUgZXhhbXBsZSBhbmQgdGhlIGNvZGUgaW4gdGhlIGZvbGxvd2luZyB0ZXN0aW5nIGFuZAphbmQgbGluZWFyIHJlZ3Jlc3Npb24gc2VjdGlvbnMgaXMgYWRhcHRlZCBmcm9tIHRoZSBvbmUgZm91bmQgCltoZXJlXShodHRwOi8vdmFyaWFuY2VleHBsYWluZWQub3JnL1JEYXRhL2Fib3V0LyNsaWNlbnNpbmcpLgoKRmlyc3Qgd2UgY2FuIHZpc3VhbGl6ZSB0aGUgb2JzZXJ2YXRpb25zIHVzaW5nIHRoZSBib3hwbG90LiBUaCBkYXRhIGFib3V0CnRoZSB0cmFuc21pc3Npb24gaXMgc3RvcmVkIGluIHRoZSBgYW1gIGNvbHVtbiBhbmQgb24gdGhlIGZ1ZWwgZWZmaWNpZW5jeQppbiB0aGUgYG1wZ2AgY29sdW1uLgoKYGBge3IgZmlnLndpZHRoPTUsIGZpZy5oZWlnaHQ9NX0KZGF0YSgibXRjYXJzIikKbXRjYXJzJGFtIDwtIGZhY3RvcihtdGNhcnMkYW0sIGxldmVscyA9IGMoMCwgMSksIAogICAgICAgICAgICAgICAgICAgIGxhYmVscyA9IGMoImF1dG9tYXRpYyIsICJtYW51YWwiKSkKZ2dwbG90KG10Y2FycywgYWVzKHggPSBhbSwgeSA9IG1wZykpICsgZ2VvbV9ib3hwbG90KCkgKwogIHhsYWIoIlRyYXNtaXNzaW9uIikgKyB5bGFiKCJGdWVsIGVmZmljaWVuY3kiKQpgYGAKClRvIHRlc3Qgd2hldGhlciB0aGUgbWVhbiBtaWxlYWdlIHBlciBnYWxsb24gaXMgZGlmZmVyZW50IGJldHdlZW4gdGhlIGNhcnMgd2l0aCAKYXV0b21hdGljIGFuZCBtYW51YWwgdHJhbnNtaXNzaW9uLCB3ZSBjYW4gdXNlIHRoZSBgdC50ZXN0KClgIGZ1bmN0aW9uOgoKYGBge3J9Cih0dCA8LSB0LnRlc3QobXBnIH4gYW0sIGRhdGE9bXRjYXJzKSkKYGBgCgpIZXJlIHRoZSBmaXJzdCBhcmd1bWVudCBpcyB0aGUgYGZvcm11bGEgPSBtcGcgfiBhbWAuIEluIFIgYSB0aWxkZSBzeW1ib2wsCmB+YCBtZWFucyAiZXhwbGFpbmVkIGJ5Ii4gVGhhdCBpcyB3ZSB3YW50IHRvIHRlc3QgdGhlIG1pbGVzIHBlcgpnYWxsb24gZXhwbGFpbmVkIGJ5IHRoZSBhdXRvbWF0aWMgdHJhbnNtaXNzaW9uLiBUaGUgc2Vjb25kIGFyZ3VtZW50IGlzIHRoZQpkYXRhc2V0IHdlIGNob29zZSwgYG10Y2Fyc2AuCgpXZSBjYW4gZXh0cmFjdCB0aGUgaW5mb3JtYXRpb24gY29tcHV0ZWQgZm9yIHRoZSB0LXRlc3Qgc3RvcmVkIGluIHRoZSBmb2xsb3dpbmcKZWxlbWVudHMgb2YgYHR0YC4KCmBgYHtyfQpuYW1lcyh0dCkKYGBgCgpXZSBjYW4gZXh0cmFjdCB0aGUgcC12YWx1ZSwgdGhhdCBpcyB0aGUgcHJvYmFiaWxpdHkgdGhhdCB3ZSB3b3VsZCBvYnNlcnZlIGEKbW9yZSBleHRyZW1lIGRpZmZlcmVuY2UgaW4gdGhlIHNhbXBsZSBtZWFucyBnaXZlbiB0aGF0IGJvdGggc2FtcGxlcyBjb21lIGZyb20KdGhlIHNhbWUgcG9wdWxhdGlvbi4gSW4gdGhpcyBjYXNlIGl0IG1lYW5zIHRoYXQgaWYgaW5kZWVkIHRoZSBhdXRvbWF0aWMgCmFuZCBtYW51YWwgdHJhbnNtaXNzaW9uIGNhcnMgaGF2ZSBlcXVhbCBhdmVyYWdlIG1pbGVhZ2UgcGVyIGdhbGxvbiByYXRlLCAKdGhlbiB0aGUgcHJvYmFiaWxpdHkgdGhhdCB3ZSB3b3VsZCBvYnNlcnZlIGEgZ3JlYXRlciBvciBlcXVhbCBkaWZmZXJlbmNlIGluIAp0aGUgc2FtcGxlIG1lYW4gYG10Z2AgaXMgZXF1YWwgdG8gcC12YWx1ZS4gIAoKYGBge3J9CnR0JHAudmFsdWUKYGBgCgpUaGUgOTUlIGNvbmZpZGVuY2UgaW50ZXJ2YWwgZm9yIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIHR3byBtZWFucyBpcwpzdG9yZWQgaW46CgpgYGB7cn0KdHQkY29uZi5pbnQKYGBgCgoKIyBTdXBlcnZpc2VkIExlYXJuaW5nCgoqICpTdXBlcnZpc2VkIExlYXJuaW5nKiBpcyBhIHRhc2sgb2YgaW5mZXJyaW5nIHRoZSByZWxhdGlvbnNoaXAgYmV0d2Vlbgp0aGUgaW5wdXQgZGF0YSBhbmQgdGhlIHJlc3BvbnNlIHZhcmlhYmxlLiAKCiogSW4gc3VwZXJ2aXNlZCBsZWFybmluZyBlYWNoIG9ic2VydmF0aW9uIGNvbnNpc3Qgb2YgYSBwYWlyICQoeCwgeSkkIAp3aGVyZSAkeCQgaXMgdGhlIGlucHV0IGRhdGEsIGUuZy4gYSBjb2xsZWN0aW9uIG9mIHRoZSBhdHRyaWJ1dGVzLCAKYW5kICR5JCB0aGUgbGFiZWwgb3IgdGhlIG91dHB1dCB2YWx1ZS4KCiogU3VwZXJ2aXNlZCBsZWFybmluZyBwcm9ibGVtcyBjYW4gYmUgZGl2aWRlZCBpbnRvIGNsYXNzaWZpY2F0aW9uIAphbmQgcmVncmVzc2lvbiB0YXNrcy4KCiAgICArICoqUmVncmVzc2lvbioqOiAkeSQgaXMgYSAqcXVhbnRpdGF0aXZlKiB2YXJpYWJsZSAobnVtZXJpY2FsL2NvbnRpbnVvdXMvb3JkZXJlZCkKICAgICAgZS5nLiBtaWxlYWdlIHBlciBnYWxsb24gaW4gdGhlIGBtdGNhcnNgIGRhdGFzZXQKICAgIAogICAgKyAqKkNsYXNzaWZpY2F0aW9uKio6ICR5JCBpcyBhICpxdWFsaXRhdGl2ZSogdmFyaWFibGUgKGNhdGVnb3JpY2FsKSAgIAogICAgICBlLmcuIHRyYW5zbWlzc2lvbiBpbiB0aGUgYG10Y2Fyc2AgZGF0YXNldAoKIyBSZWdyZXNzaW9uCgoKIyMgTGluZWFyIFJlZ3Jlc3Npb24KCiogKipMaW5lYXIgcmVncmVzc2lvbioqIGlzIGEgdHlwZSBvZiByZWdyZXNzaW9uIHdoZXJlIHRoZSBxdWFudGl0YXRpdmUKb3V0cHV0IHZhcmlhYmxlIGlzIG1vZGVsZWQgYXMgYSAqKmxpbmVhcioqIGZ1bmN0aW9uIG9mIHRoZSBpbnB1dHMuIAoKKiAqKlNpbXBsZSBsaW5lYXIgcmVncmVzc2lvbioqIHByZWRpY3RzIHRoZSBvdXRwdXQgJHkkIGZyb20gYSBzaW5nbGUgcHJlZGljdG9yIAokeCQuIFRoYXQgaXMgd2UgYXNzdW1lIHRoZSBvdXRjb21lICR5JCBmb2xsb3dzIHRoZSBmb2xsb3dpbmcgbGluZWFyIG1vZGVsLCB3aGVyZQokXGVwc2lsb24kIGlzIGEgcmFuZG9tIG5vaXNlIHRlcm0gd2l0aCB6ZXJvIG1lYW4uCgokJHkgPSBcYmV0YV8wICsgXGJldGFfMSB4ICsgXGVwc2lsb24kJAoKKiAqKk11bHRpcGxlIGxpbmVhciByZWdyZXNzaW9uKiogYXNzdW1lcyAkeSQgcmVsaWVzIG9uIG1hbnkgY292YXJpYXRlczoKCiQkeSA9IFxiZXRhXzAgKyBcYmV0YV8xIHhfMSArIFxiZXRhXzIgeF8yICsgXGRvdHMgKyBcYmV0YV9wIHhfcCArIFxlcHNpbG9uID0KXHZlYyBcYmV0YSBcY2RvdCBcdmVjIHggKyBcZXBzaWxvbiQkCgpMaW5lYXIgcmVncmVzc2lvbiBzZWVrcyBhIHNvbHV0aW9uICRcaGF0IHkgPSBcaGF0IFxiZXRhIFxjZG90IFx2ZWMgeCQgc3VjaAp0aGF0IHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIHRydWUgb3V0Y29tZSAkeSQgYW5kIHRoZSBwcmVkaWN0aW9uICRcaGF0IHkkCih0aGUgc3VtIG9mIHRoZSBzcXVhcmVkIHJlc2lkdWFscykgaXMgbWluaW1pemVkLgoKJCRhcmcgXG1pblxsaW1pdHNfe1xoYXQgXGJldGF9IFxzdW1faSBcbGVmdCh5XnsoaSl9IC0gXGhhdCBcYmV0YSB4XnsoaSl9XHJpZ2h0KV4yJCQKCiMjIyBTaW1wbGUgTGluZWFyIFJlZ3Jlc3Npb24KCkFuYWx5emluZyB0aGUgZXhhbXBsZSBkYXRhc2V0IGBtdGNhcnNgLCB3ZSBjYW4gdHJ5IHRvIG1vZGVsIHRoZSBtaWxlYWdlIHBlcgpnYWxsb24gdXNpbmcgdGhlIHdlaWdodCBvZiB0aGUgY2FyLiBUaGF0IGlzIHdlIHdvdWxkIGxpa2UgdG8gdXNlIHRoZSB3ZWlnaHQKb2YgdGhlIGNhciB0byBwcmVkaWN0IHRoZSBtcGcuIAoKSW4gUiB0aGUgbGluZWFyIG1vZGVscyBjYW4gYmUgZml0IHVzaW5nIGFuIGBsbWAgZnVuY3Rpb24uCgpgYGB7cn0KZml0IDwtIGxtKG1wZyB+IHd0LCBtdGNhcnMpCmBgYAoKTm90ZSB0aGF0IHdlIHVzZSB0aGUgc2FtZSBub3RhdGlvbiBhcyBmb3IgdGhlIGB0LnRlc3RgIGZ1bmN0aW9uLiBXZSBjYW4gY2hlY2sgCnRoZSBkZXRhaWxzIG9uIHRoZSBmaXR0ZWQgbW9kZWwgYnkgY2FsbGluZzoKCmBgYHtyfQpzdW1tYXJ5KGZpdCkKYGBgCgpUaGUgcmVzdWx0cyBhcmUgb3JnYW5pemVkIGFzIGZvbGxvd3M6CiogYENhbGxgIC0tIHRoZSBmdW5jdGlvbiBjYWxsIGZvciB0aGUgZml0dGVkIG1vZGVsLAoqIGBSZXNpZHVhbHNgIC0tIHRoZSByZXNpZHVhbHMgYmV0d2VlbiB0aGUgdHJ1ZSBtcGcgYW5kIHRoZSBwcmVkaWN0ZWQgdmFsdWVzCiogYENvZWZmaWNlbnRzYCAtLSB0aGUgZml0dGVkIGNvZWZmaWNpZW50cyBmb3IgdGhlIGZpdHRlZCBtb2RlbCAodGhlICRcYmV0YSQncyAKaW4gdGhlIGxpbmVhciBtb2RlbCBmb3JtdWxhKS4gVGhlIHZhbHVlcywgdGhlIHN0YW5kYXJkIGVycm9ycywgdGhlIHQtc3RhdGlzdGljcwphcyB3ZWxsIGFzIHRoZSBwLXZhbHVlcyBhcmUgc2hvd24uIFRoZSBzdGFycyBpbiB0aGUgbGFzdCBjb2x1bW4gbWFyayB0aGUKc2lnbmlmaWNhbmNlIG9mIGVhY2ggY29lZmZpY2llbnQgKG1vcmUgc3RhcnMgbWVhbnMgbW9yZSBpbXBvcnRhbmNlKS4KKiBPdGhlciBkZXRhaWxzIG9uIHRoZSBwZXJmb3JtYW5jZSBvZiB0aGUgbW9kZWwuCgpDb2VmZmljaWVudHMgb2YgdGhlIG1vZGVsIGNhbiBiZSBleHRyYWN0ZWQgd2l0aDoKCmBgYHtyfQooY28gPC0gIGNvZWYoc3VtbWFyeShmaXQpKSkKYGBgCgpUbyBwcmVkaWN0IHRoZSBgbXBnYCBmb3IgdGhlIGV4aXN0aW5nIG9ic2VydmF0aW9ucyAoY2FycykgeW91IGNhbiBjYWxsCgpgYGB7cn0KcHJlZGljdChmaXQpCmBgYAoKVG8gcHJlZGljdCB0aGUgYG1wZ2AgZm9yIHRoZSBuZXcgb2JzZXJ2YXRpb25zLCBlLmcuIGNhcnMgd2l0aCBzcGVjaWZpYwp3ZWlnaHRzLCBlLmcuIGB3dCA9IDMuMTRgIHdlIGNhbiB1c2UgdGhlIGNvbXB1dGVkIGNvZWZmaWNpZW50czoKCmBgYHtyfQpjb1ssIDFdCgojIGJldGEwICsgYmV0YTEgKiB3dApjb1sxLCAxXSArIGNvWzIsIDFdKiAzLjE0ICMgIDM3LjI4NTEyNiArICAoLTUuMzQ0NDcyKSAqIDMuMTQKYGBgCgpXZSBjYW4gbWFrZSBwcmVkaWN0aW9ucyBmb3IgYSBsYXJnZSBudW1iZXIgb2YgbmV3IG9ic2VydmF0aW9ucyBieSBjcmVhdGluZyAKYSBkYXRhIGZyYW1lIHdpdGggbmV3IHdlaWdodHM6CgpgYGB7cn0KbmV3Y2FycyA8LSBkYXRhLmZyYW1lKHd0ID0gYygyLCAyLjEsIDMuMTQsIDQuMSwgNC4zKSkKcHJlZGljdChmaXQsIG5ld2NhcnMpCmBgYAoKTm90ZSB0aGF0IHRoaXMgcHJvZHVjZXMgdGhlIHNhbWUgcHJlZGljdGlvbiBmb3IgYHd0ID0gMy4xNGAgYXMgd2UgY29tcHV0ZWQKcHJldmlvdXNseS4KCldlIGNhbiBwbG90IHRoZSBkYXRhIGFuZCB0aGUgZml0dGVkIG1vZGVsIHVzaW5nIGBnZ3Bsb3QyYC4gVGhpcyBjYW4gYmUKZG9uZSBldmVuIHdpdGhvdXQgY29tcHV0aW5nIHRoZSBtb2RlbCBpbiB0aGUgcHJldmlvdXMgc3RlcC4KClRoZSBgZ2VvbV9zbW9vdGhlcmAgd2l0aCB0aGUgYG1ldGhvZGAgYXJndW1lbnQgc2V0IGVxdWFsIHRvIGAibG0iYCAKZG9lcyB0aGUgY29tcHV0YXRpb25zIGF1dG9tYXRpY2FsbHkuCgpgYGB7cn0KZ2dwbG90KG10Y2FycywgYWVzKHd0LCBtcGcpKSArIGdlb21fcG9pbnQoKSArIGdlb21fc21vb3RoKG1ldGhvZD0ibG0iKQpgYGAKCiMjIyBNdWx0aXBsZSBMaW5lYXIgUmVncmVzc2lvbgoKTW9yZSBlbGFib3JhdGUgbW9kZWxzIGludm9sdmluZyBtb3JlIGlucHV0IHZhcmlhYmxlcyBjYW4gYmUgZml0dGVkIHVzaW5nIAp0aGUgc2FtZSBmdW5jdGlvbiBgbG0oKWAuCgpGb3IgZXhhbXBsZSB3ZSBjYW4gYmUgaW50ZXJlc3RlZCBpbiBwcmVkaWN0aW5nIHRoZSBgbXBnYCBmcm9tIAp3ZWlnaHQsIGRpc3BsYWNlbWVudCBhbmQgdGhlIG51bWJlciBvZiBjeWxpbmRlcnMgaW4gdGhlIGNhci4KCkxvb2sgYXQgdGhlIGRhdGE6CgpgYGB7cn0KZ2dwbG90KG10Y2FycywgYWVzKHg9d3QsIHk9bXBnLCBjb2w9Y3lsLCBzaXplPWRpc3ApKSArIGdlb21fcG9pbnQoKQpgYGAKCgoKYGBge3J9Cm1maXQxIDwtIGxtKG1wZyB+IHd0ICsgZGlzcCArIGN5bCwgZGF0YSA9IG10Y2FycykKc3VtbWFyeShtZml0MSkKYGBgCgpUaGUgc2FtZSBjb21tYW5kcyBhcyBiZWZvcmUgY2FuIGJlIGFwcGxpZWQgdG8gYHN1bW1hcnkobWZpdDEpYCB0byBleHRyYWN0IHRoZSAKaW5mb3JtYXRpb24uCgpUbyBwcmVkaWN0IGBtcGdgIGZvciBuZXcgdmFsdWVzIGNhcnMgZmlyc3QgY3JlYXRlIGEgZGF0YSBmcmFtZSBvZiBuZXcKaW5wdXRzIHBlciBjYXI6CgpgYGB7cn0KbmV3Y2FycyA8LSBkYXRhLmZyYW1lKHd0ID0gYygyLCAyLjEsIDMuMTQsIDQuMSwgNC4zKSwKICAgICAgICAgICAgICAgICAgICAgIGRpc3AgPSBjKDEwMCwgMjAwLCA1MDAsMzAwLCAyMTApLAogICAgICAgICAgICAgICAgICAgICAgY3lsID0gYyg2LDYsNCw2LDgpKQpwcmVkaWN0KG1maXQxLCBuZXdjYXJzKQpgYGAKCk1vZGVscyB3aXRoICoqaW50ZXJhY3Rpb24gZWZmZWN0cyoqIGNhbiBiZSBzcGVjaWZpZWQgd2l0aCAqOgpgYGB7cn0KbWZpdDIgPC0gbG0obXBnIH4gYW0gKiB3dCwgbXRjYXJzKQpzdW1tYXJ5KG1maXQyKQpgYGAKCgojIyBMYXNzbyBSZWdyZXNzaW9uCgpOb3dhZGF5cywgd29ya2luZyB3aXRoIHJlYWwgZGF0YXNldHMgd2UgY2FuIGVuY291bnRlciBhIHByb2JsZW0gb2YgaGF2aW5nICJ0b28iCm1hbnkgdmFyaWFibGVzLiBPbmUgZXhhbXBsZSBvZiBzdWNoIGEgcHJvYmxlbSBpcyBwcmVkaWN0aW9uIHRoZSByaXNrIG9mIGEgCmRpc2Vhc2UgYmFzZWQgb24gdGhlIHNpbmdsZSBudWNsZW90aWRlIHBvbHltb3JwaGlzbXMgKFNOUHMpIGRhdGEuIApJbiB0aGlzIGNhc2UgdGhlIG51bWJlciBvZiBwcmVkaWN0aW9ucyBjYW4gYmUgbXVjaCBsYXJnZXIgdGhhbiB0aGFuIHRoZQpudW1iZXIgb2Ygb2JzZXJ2YXRpb25zLiBMYXNzbyByZWdyZXNzaW9uIGlzIGVzcGVjaWFsbHkgdXNlZnVsIGZvciBwcm9ibGVtcywKd2hlcmUgKip0aGUgbnVtYmVyIG9mIGF2YWlsYWJsZSBjb3ZhcmlhdGVzIGlzIGV4dHJlbWVseSBsYXJnZSwgYnV0Cm9ubHkgYSBoYW5kZnVsIG9mIHRoZW0gYXJlIHJlbGV2YW50IGZvciB0aGUgcHJlZGljdGlvbiBvZiB0aGUgb3V0Y29tZSoqLgoKTGFzc28gaXMgc2ltcGx5IHJlZ3Jlc3Npb24gd2l0aCAkTF8xJCBwZW5hbHR5LiBUaGF0IGlzIHdlIGFyZSBpbnRlcmVzdGVkIGluIApmaW5kaW5nIGEgc29sdXRpb24gdG8gdGhlIGZvbGxvd2luZyBwcm9ibGVtOgoKJCRhcmcgXG1pblxsaW1pdHNfe1xoYXQgXGJldGF9IFxzdW1faSBcbGVmdCh5XnsoaSl9IAotIFxoYXQgXGJldGEgeF57KGkpfVxyaWdodCleMiArIFxsYW1iZGEgXHxcaGF0IFxiZXRhXHxfMSQkCgpJdCB0dXJucyBvdXQgdGhhdCB0aGUgJExfMSQgbm9ybSAkXHxcdmVjIHhcfF8xID0gXHN1bV9qIHx4X2p8JCBwcm9tb3RlcwpzcGFyc2l0eSB3aGljaCBtZWFucyB0aGF0IHRoZSBzb2x1dGlvbnMgZm91bmQgd2lsbCB1c3VhbGx5IGhhdmUgb25seSAKYSBzbWFsbCBudW1iZXIgb2Ygbm9uLXplcm8gY29lZmZpY2llbnRzLiBUaGUgbnVtYmVyIG9mIG5vbi16ZXJvIGNvZWZmaWNpZW50cwpkZXBlbmRzIG9uIHRoZSBjaG9pY2Ugb2YgdGhlIHR1bmluZyBwYXJhbWV0ZXIsICRcbGFtYmRhJC4gVGhlIGhpZ2hlciB0aGUKJFxsYW1iZGEkIHRoZSBmZXdlciBub24temVybyBjb2VmZmljaWVudHMuCgpMYXNzbyByZWdyZXNzaW9uIGlzIGltcGxlbWVudGVkIGluIGFuIFIgcGFja2FnZSBgZ2xtbmV0YC4gQW4gaW50cm9kdWN0b3J5CnR1dG9yaWFsIHRvIHRoZSBwYWNrYWdlIGNhbiBiZSBmb3VuZCAKW2hlcmVdKGh0dHBzOi8vd2ViLnN0YW5mb3JkLmVkdS9+aGFzdGllL2dsbW5ldC9nbG1uZXRfYWxwaGEuaHRtbCkuCgojIyMgTGFzc28gRXhhbXBsZQoKV2UgYWdhaW4gdXNlIHRoZSBgbXRjYXJzYCBkYXRhc2V0cyBmb3IgdGhlIGZvbGxvd2luZyBleGFtcGxlLiAKTm93IHdlIHdpbGwgYnVpbGQgYSBtb2RlbCBwcmVkaWN0aW5nIHRoZSBgbXBnYCB1c2luZyB0aGUgTGFzc28gcmVncmVzc2lvbi4gCldlIHN1cHBseSBhbGwgdGhlIGF2YWlsYWJsZSBjb3ZhcmlhdGVzIGFuZCBsZXQgdGhlIGFsZ29yaXRobSBmaWd1cmUgb3V0CmZpdAoKYGBge3J9CmxpYnJhcnkoZ2xtbmV0KQpoZWFkKG10Y2FycykKCnkgPC0gbXRjYXJzWywgMV0gIyBtaWxlYWdlIHBlciBnYWxsb24gCnggPC0gbXRjYXJzWywgLTFdICMgYWxsIG90aGVyIHZhcmlhYmxlcyB0cmVhdGVkIGFzIHByZWRpY3RvcnMKeCA8LSBkYXRhLm1hdHJpeCh4LCAibWF0cml4IikKCnNldC5zZWVkKDEyMykKdHJhaW5JZHggPC0gc2FtcGxlKDE6bnJvdyhtdGNhcnMpLCByb3VuZCgwLjcgKiBucm93KG10Y2FycykpKQoKZml0IDwtIGdsbW5ldCh4W3RyYWluSWR4LCBdLCB5W3RyYWluSWR4XSkKYGBgCgoKCmBgYHtyfQpwcmludChmaXQpCmBgYAoKKiBgZ2xtbmV0KClgIGNvbXB1dGUgdGhlIExhc3NvIHJlZ3Jlc3Npb24gZm9yIGEgc2VxdWVuY2Ugb2YgZGlmZmVyZW50IHR1bmluZwpwYXJhbWV0ZXJzLiAKKiBUaHVzLCBlYWNoIG9mIHRoZSByb3dzIG9mIHRoZSB0YWJsZSBhYm92ZSBjb3JyZXNwb25kcyB0byBhIHBhcnRpY3VsYXIKJFxsYW1iZGEkIGluIHRoZSBzZXF1ZW5jZS4KCkluIHRoZSBhYm92ZSB0YWJsZSBjb2x1bW4gYERmYCBkZW5vdGVzIHRoZSBudW1iZXIgb2Ygbm9uLXplcm8gY29lZmZpY2llbnRzCihkZWdyZWVzIG9mIGZyZWVkb20pLCBgJURldmAgaXMgdGhlIHBlcmNlbnRhZ2UgdmFyaWFuY2UgZXhwbGFpbmVkLCBhbmQKYExhbWJkYWAgaXMgdGhlIHZhbHVlIG9mIHRoZSBjdXJyZW50bHkgY2hvc2VuIHR1bmluZyBwYXJhbWV0ZXIuIAoKYGBge3IgZmlnLmhlaWdodD01LCBmaWcud2lkdGg9N30KcGxvdChmaXQsIGxhYmVsID0gVFJVRSkgCiMgbGFiZWwgPSBUUlVFIG1ha2VzIHRoZSBwbG90IGFubm90YXRlIHRoZSBjdXJ2ZXMgd2l0aCB0aGUgY29ycmVzcG9uZGluZyBjb2VmZmllbnRzIGxhYmVscy4KYGBgCgoqIGVhY2ggb2YgdGhlIGN1cnZlcyBhYm92ZSBjb3JyZXNwb25kcyB0byBhIHZhcmlhYmxlLiBJdCBzaG93cyB0aGF0IHBhdGggb2YgYQpzcGVjaWZpYyBjb2VmZmljaWVudCBhcyB0aGUgdmFsdWUgb2YgdGhlIHR1bmluZyBwYXJhbWV0ZXIgY2hhbmdlcywgYW5kIHRoZSAkTF8xJCAKbm9ybSBvZiB0aGUgd2hvbGUgY29lZmZpY2llbnQgdmVjdG9yIGluY3JlYXNlcy4gCiogdGhlIHR1bmluZyBwYXJhbWV0ZXIgZGVjcmVhc2VzIGZyb20gbGVmdCB0byByaWdodCwgdGhhdCBpcyB3aXRoIGEgc21hbGwgCiRcbGFtYmRhJCAocmlnaHQpIHdlIGhhdmUgbW9yZSBub24temVybyBjb2VmZmljaWVudHMuCiogdGhlIHktYXhpcyBjb3JyZXNwb25kcyB0aGUgdmFsdWUgb2YgdGhlIGNvZWZmaWNpZW50LgoqIHRoZSB4LWF4aXMgaXMgcmVsYXRlZCB0byB0aGUgJExfMSQgbm9ybSBhcyBub3RlZCwgYnV0IGlzIHNjYWxlZCB0byBpbmRpY2F0ZQp0aGUgbnVtYmVyIG9mIG5vbi16ZXJvIGNvZWZmaWNpZW50cyBmb3IgdGhlIGN1cnJlbnQgY2hvaWNlIG9mICRcbGFtYmRhJCwgd2hpY2gKaXMgZXF1YWwgdG8gdGhlIGVmZmVjdGl2ZSBkZWdyZWVzIG9mIGZyZWVkb20gKGRmKSBmb3IgdGhlIExhc3NvLgoKVGhlIGNvbXB1dGVkIExhc3NvIGNvZWZmaWNpZW50IGZvciBhIHBhcnRpY3VsYXIgY2hvaWNlIG9mICRcbGFtYmRhJCBjYW4gYmUKcHJpbnRlZCB1c2luZzoKCmBgYHtyfQpjb2VmKGZpdCwgcyA9IDEpCmBgYAoKClNpbWlsYXJseSB0byB0aGUgY2FzZSB3aXRoIGBsbSgpYCwgd2UgY2FuIHVzZSB0aGUgZnVuY3Rpb24gYHByZWRpY3QoKWAgdG8gCnByZWRpY3QgdGhlIG91dGNvbWUgZnJvbSB0aGUgZXhpc3Rpbmcgb3IgbmV3IGlucHV0IGRhdGEuIFdlIGhhdmUgdG8gaG93ZXZlcgpzcGVjaWZ5IHRoZSBjaG9pY2Ugb2YgdGhlIHR1bmluZyBwYXJhbWV0ZXIgYnkgc2V0dGluZyB0aGUgdmFsdWUgb2YgdGhlIAphcmd1bWVudCBgc2AuCgoKYGBge3J9CnByZWRpY3QoZml0LCBuZXd4ID0geFstdHJhaW5JZHgsIF0sIHMgPSBjKDAuNSwgMS41LCAyKSkKYGBgCgpFYWNoIG9mIHRoZSBjb2x1bW5zIGNvcnJlc3BvbmRzIHRvIGNvcnJlc3BvbmRpbmcgY2hvaWNlIG9mICRcbGFtYmRhJC4KClRoZSBjaG9pY2Ugb2YgJFxsYW1iZGEkIGNhbiBiZSBtYWRlIHVzaW5nIApbY3Jvc3MtdmFsaWRhdGlvbl0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvQ3Jvc3MtdmFsaWRhdGlvbl8oc3RhdGlzdGljcykpLgpXZSBjYW4gdXMgdGhlIGZ1bmN0aW9uIGBjdi5nbG1uZXQoKWAgdG8gcGVyZm9ybSBhIGstZm9sZCBjcm9zcyB2YWxpZGF0aW9uLgoKPiBJbiBrLWZvbGQgY3Jvc3MtdmFsaWRhdGlvbiwgdGhlIG9yaWdpbmFsIHNhbXBsZSBpcyByYW5kb21seSBwYXJ0aXRpb25lZCBpbnRvIAprIGVxdWFsIHNpemVkIHN1YnNhbXBsZXMuIE9mIHRoZSBrIHN1YnNhbXBsZXMsIGEgc2luZ2xlIHN1YnNhbXBsZSBpcyByZXRhaW5lZCAKYXMgdGhlIHZhbGlkYXRpb24gZGF0YSBmb3IgdGVzdGluZyB0aGUgbW9kZWwsIGFuZCB0aGUgcmVtYWluaW5nIGsg4oiSIDEgCnN1YnNhbXBsZXMgYXJlIHVzZWQgYXMgdHJhaW5pbmcgZGF0YS5eW2h0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0Nyb3NzLXZhbGlkYXRpb25fKHN0YXRpc3RpY3MpI2stZm9sZF9jcm9zcy12YWxpZGF0aW9uXQoKCmBgYHtyfQpzZXQuc2VlZCgxKQpjdmZpdCA8LSBjdi5nbG1uZXQoeFt0cmFpbklkeCwgXSwgeVt0cmFpbklkeF0sIG5mb2xkcyA9IDUpCmBgYAoKYG5mb2xkc2AgYXJndW1lbnQgc2V0cyB0aGUgbnVtYmVyIG9mIGZvbGRzIChrKS4KCmBgYHtyfQpwbG90KGN2Zml0KQpgYGAKClRoZSBhYm92ZSBwbG90IHNob3dzIHRoZSBhdmVyYWdlIE1TRSAocmVkIGRvdHMpIG92ZXIgdGhlIGZvbGRzLCB0b2dldGhlcgp3aXRoIHRoZSBzdGFuZGFyZCBkZXZpYXRpb24gYm91bmRzIChlcnJvciBiYXJzKSBmb3IKdGhlICRcbGFtYmRhJCBzZXF1ZW5jZS4gVGhlIHR3byBjaG9zZW4gJFxsYW1iZGEkIHZhbHVlcyBhcmUgaW5kaWNhdGVkIHdpdGggCmRvdHRlZCBibGFjayBsaW5lcy4KClRoZSBmaXJzdCBvbmU6CmBgYHtyfQpjdmZpdCRsYW1iZGEubWluCmBgYAoKaXMgdGhlIHZhbHVlIG9mICRcbGFtYmRhJCB0aGF0IGdpdmVzIGEgbWluaW11bSBtZWFuIGNyb3NzLXZhbGlkYXRlZCBlcnJvciwKYW5kIHRoZSBzZWNvbmQ6CgpgYGB7cn0KY3ZmaXQkbGFtYmRhLjFzZQpgYGAKCmdpdmVzIHRoZSBiaWdnZXN0ICRcbGFtYmRhJCBzdWNoIHRoYXQgdGhlIE1TRSBpcyB3aXRoaW4gb25lIHN0YW5kYXJkIGVycm9yIApvZiB0aGUgbWluaW11bSBlcnJvci4KCgojIEV4ZXJjaXNlIEkKCkluIHRoaXMgZXhlcmNpc2UgeW91IHdpbGwgcGVyZm9ybSBMYXNzbyByZWdyZXNzaW9uIHlvdXJzZWxmLgpXZSB3aWxsIHVzZSB0aGUgYEJvc3RvbmAgZGF0YXNldCBmcm9tIHRoZSBgTUFTU2AgcGFja2FnZS4KVGhlIGRhdGFzZXQgY29udGFpbnMgaW5mb3JtYXRpb24gb24gdGhlIEJvc3RvbiBzdWJ1cmJzIApob3VzaW5nIG1hcmtldCBjb2xsZWN0ZWQgYnkgRGF2aWQgSGFycmlzb24gaW4gMTk3OC4KCldlIHdpbGwgdHJ5IHRvIHByZWRpY3QgdGhlIG1lZGlhbiB2YWx1ZSBvZiBvZiBob21lcyBpbiB0aGUgcmVnaW9uIGJhc2VkIG9uIAppdHMgYXR0cmlidXRlcyByZWNvcmRlZCBpbiBvdGhlciB2YXJpYWJsZXMuCgpgYGB7cn0KbGlicmFyeShNQVNTKQo/Qm9zdG9uCmhlYWQoQm9zdG9uKQpkaW0oQm9zdG9uKQpgYGAKCmBgYHtyfQpzZXQuc2VlZCgxMjMpCnRyYWluSWR4IDwtIHNhbXBsZSgxOm5yb3coQm9zdG9uKSwgcm91bmQoMC43ICogbnJvdyhCb3N0b24pKSkKYm9zdG9uLnRlc3QgPC0gQm9zdG9uWy10cmFpbklkeCwibWVkdiJdCmBgYAoKUGVyZm9ybSBhIExhc3NvIHJlZ3Jlc3Npb24gd2l0aCBgZ2xtbmV0YC4gU3RlcHM6CgoxLiBFeHRyYWN0IHRoZSBpbnB1dCBhbmQgb3V0cHV0IGRhdGEgZnJvbSB0aGUgYEJvc3RvbmAgYGRhdGEuZnJhbWVgIGFuZCBjb252ZXJ0CnRoZW0gaWYgbmVjZXNzYXJ5IHRvIGEgY29ycmVjdCBmb3JtYXQuCjIuIFVzZSBjcm9zcy12YWxpZGF0aW9uIHRvIHNlbGVjdCB0aGUgdmFsdWUgZm9yICRcbGFtYmRhJC4KMy4gSW5zcGVjdCB0aGUgY29lZmZpY2llbnRzIGNvbXB1dGVkLgo0LiBDb21wdXRlIHRoZSBwcmVkaWN0aW9ucyBmb3IgdGhlIHRlc3QgZGF0YXNldC4gRXZhbHVhdGUgdGhlIE1TRS4KCgpgYGB7cn0KIyAoLi4uID8pCmBgYAoKCiMgQ2xhc3NpZmljYXRpb24KCiogQXMgbWVudGlvbmVkIGJlZm9yZSB1bmxpa2UgcmVncmVzc2lvbiwgY2xhc3NpZmljYXRpb24gZGVhbHMgd2l0aCBwcmVkaWN0aW9uIApvdXRjb21lcyBvciByZXNwb25zZSB2YXJpYWJsZXMgdGhhdCBhcmUgcXVhbGl0YXRpdmUsIG9yIGNhdGVnb3JpY2FsLgoKKiBUaGUgdGFzayBpcyB0byAqKmNsYXNzaWZ5Kiogb3IgYXNzaWduIGVhY2ggb2JzZXJ2YXRpb24gdG8gYSBjYXRlZ29yeSBvciBhIGNsYXNzLgoKKiBFeGFtcGxlcyBvZiBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtcyBpbmNsdWRlOgogICAgKyBwcmVkaWN0aW5nIHdoYXQgbWVkaWNhbCBjb25kaXRpb24gb3IgZGlzZWFzZSBhIHBhdGllbnQgaGFzIGJhc2Ugb24gdGhlaXIKICAgIHN5bXB0b21zLAogICAgKyBkZXRlcm1pbmluZyBjZWxsIHR5cGVzIGJhc2VkIG9uIHRoZWlyIGdlbmUgZXhwcmVzc2lvbiBwcm9maWxlcwogICAgKHNpbmdsZSBjZWxsIFJOQS1zZXEgZGF0YSkuCiAgICArIGRldGVjdGluZyBmcmF1ZHVsZW50IHRyYW5zYWN0aW9ucyBiYXNlZCBvbiB0aGUgdHJhbnNhY3Rpb24gaGlzdG9yeQoKIyMgTG9naXN0aWMgUmVncmVzc2lvbgoKKiBEZXNwaXRlIGl0cyBuYW1lLCAqbG9naXN0aWMgcmVncmVzc2lvbiogaXMgdXNlZCBmb3IgY2xhc3NpZmljYXRpb24gcHJvYmxlbXMuCgoqIEl0IHBlcmZvcm1zIGJpbmFyeSBjbGFzc2lmaWNhdGlvbiAob25seSB0d28gY2F0ZWdvcmllcyksCgoqIFRoZSBuYW1lICpyZWdyZXNzaW9uKiBpcyBkdWUgdG8gdGhlIGZhY3QgdGhhdCB3ZSBhcmUgc3RpbGwgZml0dGluZyAKYSBmdW5jdGlvbiB0byB0aGUgZGF0YS4gSG93ZXZlciwgaW4gdGhpcyBjYXNlLCB3ZSBhcmUgaW50ZXJlc3RlZAppbiB0aGUgcmVsYXRpb25zaGlwIGJldHdlZW4gdGhlIGlucHV0IGFuZCB0aGUgKipwcm9iYWJpbGl0eSoqIHRoYXQgCnRoZSBvdXRwdXQgaXMgaW4gb25lIG9mIHRoZSB0d28gY2xhc3NlcyBhbmQgbm90IHRoZSBjbGFzcyBhc3NpZ21uZW50IGl0c2VsZi4gClRoaXMgZnVuY3Rpb24gdXNlZCB0byBtb2RlbCB0aGUgcmVsYXRpb25zaGlwIGlzIGNhbGxlZCBhICoqbG9naXQgZnVuY3Rpb24qKjoKCiQkUFt5ID0gMSB8IHhdID0ge1xleHBee1xiZXRhXzAgKyBcYmV0YV8xIHh9IFxvdmVyIDEgKyBcZXhwXntcYmV0YV8wICsgXGJldGFfMSB4fX0kJAoKIVtdKC4vZmlndXJlcy9sb2dpdC5wbmcpCgojIyBMb2dpc3RpYyBSZWdyZXNzaW9uIEV4YW1wbGUKCldlIGdvIGJhY2sgdG8gdGhlIGBtdGNhcnNgIGRhdGFzZXQuCgpgYGB7cn0KaGVhZChtdGNhcnMpCmBgYAoKVXNpbmcgbG9naXN0aWMgcmVncmVzc2lvbiB3ZSB3aWxsIHRyeSB0byBwcmVkaWN0IHdoZXRoZXIgYSBjYXIgaGFkIG1hbmlhbCBvciAKYXV0b21hdGljIHRyYW5zbWlzc2lvbiBiYXNlIG9uIGl0cyBvdGhlciBjaGFyYWN0ZXJpc3RpY3MuCgpJbiBSIHRoZSBmdW5jdGlvbiBgZ2xtKClgIGNhbiBiZSB1c2VkIHRvIHBlcmZvcm0gbG9naXN0aWMgcmVncmVzc2lvbgooYXMgd2VsbCBhcyBtYW15IG90aGVyIGdlbmVyYWxpemVkIGxpbmVhciBtb2RlbHMgd2hpY2ggeW91IGNhbiBsb29rIHVwCmJ5IGNhbGxpbmcgYD9nbG1gKQoKTm90ZSB0aGF0IGN1cnJlbnRseSB0aGUgY29sdW1uIGBhbWAgaW4gYG10Y2Fyc2AgaXMgYSBudW1lcmljYWwgdmFyaWFibGUuCkhvd2V2ZXIsIGl0cyB2YWx1ZXMgYXJlIG9ubHkgMCBvciAxIGRlbm90aW5nIGF1dG9tYXRpYyBvciBtYW51YWwgdHJhbnNtaXNzaW9uCnJlc3BlY3RpdmVseS4KYGBge3J9CmNsYXNzKG10Y2FycyRhbSkKdGFibGUobXRjYXJzJGFtKQpgYGAKCldlIG5lZWQgdG8gY29udmVydCB0aGF0IGNvbHVtbiB0byBhIGZhY3RvciBmb3JtYXQsIHNvIHRoYXQgUiBrbm93cyB0aGUgYGFtYAp2YXJpYWJsZSBpcyBhIGNhdGVnb3JpY2FsIG9uZToKCmBgYHtyfQptdGNhcnMkYW0gPC0gZmFjdG9yKG10Y2FycyRhbSkKYGBgCgoKVGhlbiB3ZSBmaXQgdGhlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gcHJlZGljYXRpbmcgdGhlIHRyYW5zbWlzc2lvbiBvZiB0aGUgY2FyCmZyb20gaXRzIG1pbGVhZ2UgcGVyIGhvdXIgKGBtcGdgKSBhbmQgdGhlIGdyb3NzIGhvcmVzZXBvd2VyIChgaHBgKQp3aXRoIHRoZSBmb2xsb3dpbmcgZnVuY3Rpb24gY2FsbDoKCmBgYHtyfQpmaXQubG9naXQgPC0gZ2xtKGFtIH4gbXBnICsgaHAsIGRhdGEgPSBtdGNhcnMsIGZhbWlseSA9ICJiaW5vbWlhbCIpIApgYGAKCk5vdGUgdGhhdCB0aGUgZm9ybXVsYSBgYW0gfiAuYCBtZWFucyB3ZSBhcmUgaW50ZXJlc3RlZCBpbiBleHBsYWluaW5nIGB+YCB0aGUKdmFyaWFibGUgYGFtYCB3aXRoIGBtcGdgIGFuZCBgaHBgLgpZb3UgbmVlZCB0byBzZXQgdGhlIGZhbWlseSB0byBgZmFtaWx5ID0gImJpbm9taWFsImAgdG8gaW5kaWNhdGUgeW91IHdvdWxkCmxpa2UgdG8gcGVyZm9ybSBhIGxvZ2lzdGljIHJlZ3Jlc3Npb24uIE1vcmUgb24gdGhpcyBgZmFtaWx5YCBwYXJhbWV0ZXIsIHdoaWNoCmRlc2NyaWJlcyB0aGUgZXJyb3IgZGlzdHJpYnV0aW9uIGFuZCB0aGUgbGluayBmdW5jdGlvbiBjYW4gYmUgCmZvdW5kIGJ5IGNhbGxpbmcgYD9mYW1pbHlgLiAKClRoZSBtb2RlbCBzdW1tYXJ5IGNhbiBiZSBwcmludGVkIHdpdGg6CgpgYGB7cn0Kc3VtbWFyeShmaXQubG9naXQpCmBgYAoKQXMgd2Ugc2VlIHRoZSBvdXRwdXQgaXMgc2ltbWlsYXIgdG8gdGhlIG9uZSBmb3IgdGhlIGxpbmVhciBtb2RlbCwgaW5jbHVkaW5nCnRoZSBmdW5jdGlvbiBjYWxsLCBpbmZvcm1hdGlvbiBvbiByZXNpZHVhbHMsIGNvZWZmaWNpZW50IG1hdHJpeCBldGMuCgpQcmVkaWN0aW9ucyBjYW4gYmUgY29tcHV0ZWQgYWdhaW4gdXNpbmcgYHByZWRpY3QoKWAgZnVuY3Rpb24sIHdpdGggdGhlIGFyZ3VtZW50CmB0eXBlID0gInJlc3BvbnNlImAuCgpgYGB7cn0KKG5ld2NhcnMgPC0gZGF0YS5mcmFtZShtcGcgPSBtZWFuKG10Y2FycyRtcGcpLAogICAgICAgICAgICAgICAgICAgICAgaHAgPSBjKDExMCwgMTcwLCAxNTUpKSkKYGBgCgpgYGB7cn0KcHJlZGljdChmaXQubG9naXQsIG5ld2RhdGEgPSBuZXdjYXJzLCB0eXBlID0gInJlc3BvbnNlIikKYGBgCgpJbiB0aGUgYWJvdmUgdGhlIG91dHB1dCB0aGlzIHRoZSBwcm9iYWJpbGl0eSBvZiBhIG5ldyBjYXIgd2l0aCBzcGVjaWZpZWQKbXBnIGFuZCBocCB0byBoYXZlIGEgbWFudWFsIHRyYW5zbWlzc2lvbiAod2ljaCBjb3JyZXNwb25kcyB0byB2YWx1ZQpvZiAxIGluIHRoZSBmYWN0b3IgYG10Y2FycyRhbWApLiBDbGFzc2lmaWNhdGlvbiBjYW4gYmUgZG9uZSBieQphc3NpZ25pbmcgIm1hbnVhbCIgdG8gYWxsIHRoZSBjYXJzIHdpdGggdGhlIHByb2JhYmlsaXR5ID4gMC41LCBhbmQgImF1dG9tYXRpYyIKdG8gdGhlIHJlc3QuCgpNb3JlIG9uIGxvZ2lzdGljIHJlZ3Jlc3Npb24gaW4gUiBjYW4gYmUgZm91bmQgW2hlcmVdKGh0dHA6Ly93d3cuYXRzLnVjbGEuZWR1L3N0YXQvci9kYWUvbG9naXQuaHRtKQoKCiMjIFN1cG9ydCBWZWN0b3IgTWFjaGluZXMgKFNWTSkKCiogVGhlIGZvbGxvd2luZyB2aWRlb3MgY29udGF0aSBhIGJyaWVmIGV4cGxhbmF0aW9uIG9mIHRoZSBwcmluY2lwbGUgb2YgdGhlIFNWTXM6CiAgKyBbdmlkZW9dKGh0dHBzOi8vd3d3LnlvdXR1YmUuY29tL3dhdGNoP3Y9NXpSbWhPVWpqR1kpCiAgKyBbbGVjdHVyZXNdKGh0dHBzOi8vd3d3LnlvdXR1YmUuY29tL3dhdGNoP3Y9d2ZLR0V6dzB0U2MmbGlzdD1QTHBXdm1kZHJTd2lISXl4SnEwaHdfOWI4dzJqX3NXT1ZlKSBieSBBbmRyZXcgTmcKCgohW10oLi9maWd1cmVzL1NWTV9vcHRpbWl6ZS5wbmcpCgojIyMgU3VwcG9ydCBWZWN0b3JzCgohW10oLi9maWd1cmVzL3N1cHBvcnRfdmVjcy5wbmcpCgojIyMgS2VybmVsIFNWTQoKIVtdKC4vZmlndXJlcy9LZXJuZWxfTWFjaGluZS5wbmcpCgojIyBTVk0gRXhhbXBsZQoKV2Ugd2lsbCBkbyBhIHNpbXBsZSBleGFtcGxlIGZyb20gdGhlIElTTCBjb21wdXRpbmcgU1ZNIG9uIGEgc2ltdWxhdGVkIGRhdGE6CgpgYGB7cn0Kc2V0LnNlZWQoMSkKeCA8LSBtYXRyaXgocm5vcm0oMjAqMiksIG5jb2w9MikKeSA8LSBjKHJlcCgtMSwxMCksIHJlcCgxLDEwKSkKeFt5ID09IDEsXSA8LSB4W3kgPT0gMSwgXSArIDEKcGxvdCh4LCBjb2w9KDMteSkpCmRhdCA8LSBkYXRhLmZyYW1lKHggPSB4LCB5PWFzLmZhY3Rvcih5KSkKaGVhZChkYXQpCmBgYAoKYGBge3J9CmxpYnJhcnkoZTEwNzEpCnN2bWZpdCA8LSBzdm0oeSB+IC4sIGRhdGE9ZGF0LCBrZXJuZWw9ImxpbmVhciIsIGNvc3Q9MTAsIHNjYWxlPUZBTFNFKQpwbG90KHN2bWZpdCwgZGF0KQpgYGAKCgpgYGB7cn0Kc3ZtZml0JGluZGV4CnN1bW1hcnkoc3ZtZml0KQpgYGAKCmBgYHtyfQpzdm1maXQgPC0gc3ZtKHl+LiwgZGF0YT1kYXQsIGtlcm5lbD0ibGluZWFyIiwgY29zdD0wLjEsc2NhbGU9RkFMU0UpCnBsb3Qoc3ZtZml0LCBkYXQpCnN2bWZpdCRpbmRleApzZXQuc2VlZCgxKQpgYGAKClRvIGZpbmQgYSBiZXN0IGNob2ljZSBvZiB0aGUgdHVuaW5nIHBhcmFtZXRlciAiQyIgdXNlIHRoZSBgdHVuZSgpYCBmdW5jdGlvbgoKYGBge3J9CnNldC5zZWVkKDEpCnR1bmUub3V0IDwtIHR1bmUoc3ZtLHkgfiAuLCBkYXRhPWRhdCwga2VybmVsPSJsaW5lYXIiLAogICAgICAgICAgICAgICAgIHJhbmdlcz1saXN0KGNvc3Q9YygwLjAwMSwgMC4wMSwgMC4xLCAxLDUsMTAsMTAwKSkpCnN1bW1hcnkodHVuZS5vdXQpCmBgYAoKYGBge3J9CmJlc3Rtb2QgPC0gdHVuZS5vdXQkYmVzdC5tb2RlbApzdW1tYXJ5KGJlc3Rtb2QpCmBgYApXZSBidWlsZCBhIG5ldyB0ZXN0IGRhdGFzZXQgZnJvbSBhIHNpbWlsYXIgbW9kZWwgYXMgd2UgZGlkIGZvciB0aGUgdHJhaW4gZGF0YS4KCmBgYHtyfQp4dGVzdCA8LSBtYXRyaXgocm5vcm0oMjAqMiksIG5jb2w9MikKeXRlc3QgPC0gc2FtcGxlKGMoLTEsMSksIDIwLCByZXA9VFJVRSkKeHRlc3RbeXRlc3Q9PTEsIF0gPC0geHRlc3RbeXRlc3QgPT0gMSxdICsgMQp0ZXN0ZGF0IDwtIGRhdGEuZnJhbWUoeD14dGVzdCwgeT1hcy5mYWN0b3IoeXRlc3QpKQpwbG90KHh0ZXN0LCBjb2w9KDMteXRlc3QpKQpgYGAKCmBgYHtyfQp5cHJlZCA8LSBwcmVkaWN0KGJlc3Rtb2QsIHRlc3RkYXQpCnRhYmxlKHByZWRpY3QgPSB5cHJlZCwgdHJ1dGggPSB0ZXN0ZGF0JHkpCmBgYAoKQW5kIGZvciB0aGUgbm9uLXR1bmVkIG1vZGVsIHdlIGhhdmU6CgpgYGB7cn0Kc3ZtZml0IDwtIHN2bSh5fi4sIGRhdGE9ZGF0LCBrZXJuZWwgPSAibGluZWFyIiwgY29zdD0uMDEsIHNjYWxlID0gRkFMU0UpCnlwcmVkIDwtIHByZWRpY3Qoc3ZtZml0LCB0ZXN0ZGF0KQp0YWJsZShwcmVkaWN0ID0geXByZWQsIHRydXRoID0gdGVzdGRhdCR5KQpgYGAKCgojIyMgS2VybmVsIFNWTQoKTm93IHN1cHBvc2Ugd2UgaGF2ZSBub24tbGluZWFybHkgc2VwYXJhYmxlIGRhdGE6CgpgYGB7cn0Kc2V0LnNlZWQoMTIzKQojIEdlbmVyYXRlIDIwMCBwb2ludHMKeCA8LSBtYXRyaXgocm5vcm0oMjAwKjIpLCBuY29sPTIpCnhbMToxMDAsXSA8LSB4WzE6MTAwLF0rMgp4WzEwMToxNTAsXSA8LSB4WzEwMToxNTAsXS0yCnkgPC0gIGMocmVwKDEsMTUwKSwgcmVwKDIsNTApKQpkYXQgPC0gZGF0YS5mcmFtZSh4ID0geCwgeSA9IGFzLmZhY3Rvcih5KSkKcGxvdCh4LCBjb2w9eSkKCiMgTGV0IGEgcmFuZG9tIGhhbGYgYmUgYSB0cmFpbmluZyBzZXQKdHJhaW4gPC0gc2FtcGxlKDIwMCwgMTAwKQpgYGAKV2Ugd2lsbCB1c2UgdGhlIFNWTSB3aXRoICoqYSByYWRpYWwga2VybmVsKiouIE5vdGUgdGhhdCBoZXJlIHdlIGNhbiBhZGRpdGlvbmFsbHkgCnNwZWNpZnkgdGhlIGBnYW1tYWAgcGFyYW1ldGVyIGZvciB0aGUgcmFkaWFsIGZ1bmN0aW9uOgoKYGBge3J9CnN2bWZpdCA8LSBzdm0oeX4uLCBkYXRhPWRhdFt0cmFpbixdLCBrZXJuZWwgPSAicmFkaWFsIiwgIGdhbW1hPTEsIGNvc3Q9MSkKcGxvdChzdm1maXQsIGRhdFt0cmFpbixdKQpgYGAKCmBgYHtyfQpzdW1tYXJ5KHN2bWZpdCkKdGFibGUodHJ1ZSA8LSBkYXRbLXRyYWluLCJ5Il0sIHByZWQ9cHJlZGljdChzdm1maXQsIG5ld3ggPSBkYXRbLXRyYWluLF0pKQpgYGAKCgpXZSBjYW4gdHVuZSBib3RoIGBnYW1tYWAgYW5kIGBjb3N0YCBwYXJhbWV0ZXJzOgoKYGBge3J9CnNldC5zZWVkKDE3KQp0dW5lLm91dCA8LSB0dW5lKHN2bSwgeX4uLCBkYXRhPWRhdFt0cmFpbixdLCBrZXJuZWw9InJhZGlhbCIsIAogICAgICAgICAgICAgIHJhbmdlcz1saXN0KGNvc3Q9YygwLjEsMSwxMCwxMDAsMTAwMCksIGdhbW1hPWMoMC41LDEsMiwzLDQpKSkKc3VtbWFyeSh0dW5lLm91dCkKYGBgCgpgYGB7cn0KdGFibGUodHJ1ZSA8LSBkYXRbLXRyYWluLCJ5Il0sIHByZWQ9cHJlZGljdCh0dW5lLm91dCRiZXN0Lm1vZGVsLG5ld3g9ZGF0Wy10cmFpbixdKSkKYGBgCgpgYGB7cn0KcGxvdCh0dW5lLm91dCRiZXN0Lm1vZGVsLCBkYXRbdHJhaW4sXSkKYGBgCgoKIyBSYW5kb20gRm9yZXN0CgoqIEFuIGVuc2VtYmxlIGxlYXJuaW5nIG1ldGhvZCBiYXNlZCBvbiBDQVJUIChjbGFzc2lmaWNhdGlvbiBhbmQgcmVncmVzc2lvbiB0cmVlcykgCnByb3Bvc2VkIGJ5IFtCcmVpbm1hbl0oaHR0cDovL2xpbmsuc3ByaW5nZXIuY29tL2FydGljbGUvMTAuMTAyMy9BOjEwMTA5MzM0MDQzMjQpIAppbiAyMDAxLgoqIENhbiBiZSB1c2VkIHRvIHBlcmZvcm0gKipjbGFzc2lmaWNhdGlvbiBBTkQgcmVncmVzc2lvbioqCiogQSBnb29kIHdyaXRlLXVwIGlzIGF2YWlsYWJsZSBvbiBob3cgUkYgd29yawpbaGVyZV0oaHR0cDovL3d3dy5iaW9zLnVuYy5lZHUvfmR6ZW5nL0JJT1M3NDAvcmFuZG9tZm9yZXN0LnBkZikKCgojIyBEZWNpc2lvbiB0cmVlcwoKRGVjaXNpb24gdHJlZSBvbiBjbGFzc2lmaWNhdGlvbiBvZiBUaXRhbmljIFN1cnZpdm9yczoKCiFbXSguL2ZpZ3VyZXMvQ0FSVF90cmVlX3RpdGFuaWNfc3Vydml2b3JzLnBuZykKClNvdXJjZTogW3dpa2ldKGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0RlY2lzaW9uX3RyZWVfbGVhcm5pbmcpCgojIyBFbnNhbWJsZSBNZXRob2RzCgohW0VTTF0oLi9maWd1cmVzL2Vuc2VtYmxlVHJlZXMucG5nKQoKIVtdKC4vZmlndXJlcy9yYW5kb21Gb3Jlc3QuanBnKQoKU291cmNlOiBbbGlua10oaHR0cDovL3d3dy5zbGlkZXNoYXJlLm5ldC9zYXRuYW03NC9pbmRpYS1zb2Z0d2FyZS1kZXZlbG9wZXJzLWNvbmZlcmVuY2UtMjAxMy1iYW5nYWxvcmUpCgoqIEF2ZXJhZ2luZyBvdmVyIGEgY29sbGVjdGlvbiBvZiBkZWNpc2lvbiB0cmVlcyBtYWtlcyB0aGUgcHJlZGljdGlvbnMKbW9yZSBzdGFibGUuIAoKKiBPbmUgb2YgdGhlIHJhbmRvbSBmb3Jlc3QgZmVhdHVyZXMgd2hpY2ggbWFrZXMgaXQgcGVyZm9ybQp3ZWxsLCBpcyAqKnRoZSBpbnRyb2R1Y3Rpb24gb2YgcmFuZG9tbmVzcyBpbnRvIHRoZSBjYW5kaWRhdGUgc3BsaXR0aW5nIHZhcmlhYmxlcyoqLAp3aGljaCByZWR1Y2VzIGNvcnJlbGF0aW9uIGJldHdlZW4gdGhlIGdlbmVyYXRlZCB0cmVlcy4gCgoqIFdoYXQgdGhpcyBtZWFucyBpcyB0aGF0LCBhdCBlYWNoIHNwbGl0dGluZyBsZXZlbHMsIHRoZSBwb29sIG9mIHRoZSBwb3RlbnRpYWwKc3BsaXR0aW5nIHZhcmlhYmxlcyBkb2VzIG5vdCBjb250YWluIGFsbCB2YXJpYWJsZXMsIGJ1dCBvbmx5IGEgcmFuZG9tIHN1YnNldCBvZiB0aGVtLgoKCkluIFIgcmFuZG9tIGZvcmVzdCBjYW4gYmUgY29tcHV0ZWQgd2l0aCB0aGUgZnVuY3Rpb24gYHJhbmRvbUZvcmVzdCgpYCBpbiAKYHJhbmRvbUZvcmVzdGAgcGFja2FnZS4gVGhlcmUgYXJlIHR3byBpbXBvcnRhbnQgcGFyYW1ldGVycyBmb3IKYSByYW5kb20gZm9yZXN0IHByZWRpY3Rpb246CgoqIGBtdHJ5YCAtLSBOdW1iZXIgb2YgdmFyaWFibGVzIHJhbmRvbWx5IHNhbXBsZWQgYXMgY2FuZGlkYXRlcyBhdCBlYWNoIHNwbGl0LiAKKiBgbnRyZWVgLS0gTnVtYmVyIG9mIHRyZWVzIGdlbmVyYXRlZCAodG8gYmUgYXZlcmFnZWQgb3ZlcikuIAoKIVtdKC4vZmlndXJlcy9yZnBhcmFtcy5wbmcpCgpXZSB3aWxsIHVzZSB0aGUgYGlyaXNgIGRhdGFzZXQgdG8gc2hvdyBob3cgY2xhc3NpZmljYXRpb24gY2FuIGJlIGRvbmUKd2l0aCBgcmFuZG9tRm9yZXN0KClgLiBSZWdyZXNzaW9uIGNhbiBiZSBkb25lIHVzaW5nIHRoZSBzYW1lIGZ1bmN0aW9uIGNhbGxzLgoKPiAqKklyaXMqKiBpcyBhIGZhbW91cyAoRmlzaGVyJ3Mgb3IgQW5kZXJzb24ncykgZGF0YSBzZXQgZ2l2ZXMgdGhlIG1lYXN1cmVtZW50cyAKaW4gY2VudGltZXRlcnMgb2YgdGhlIHZhcmlhYmxlcyBzZXBhbCBsZW5ndGggYW5kIHdpZHRoIGFuZCBwZXRhbCBsZW5ndGggYW5kIAp3aWR0aCwgcmVzcGVjdGl2ZWx5LCBmb3IgNTAgZmxvd2VycyBmcm9tIGVhY2ggb2YgMyBzcGVjaWVzIG9mIGlyaXMuIApUaGUgc3BlY2llcyBhcmUgSXJpcyBzZXRvc2EsIHZlcnNpY29sb3IsIGFuZCB2aXJnaW5pY2EuCgpgYGB7cn0KIyMgQ2xhc3NpZmljYXRpb246CmRhdGEoaXJpcykKCiMgc2V0IHNlZWQgZm9yIHJlcHJvZHVjaWJpbGl0eSBzaW5jZSByYW5kb20gZm9yZXN0IGlzIGEgcmFuZG9tIHByZWRpY3RvciAKc2V0LnNlZWQoNzEpIAppcmlzLnJmIDwtIHJhbmRvbUZvcmVzdChTcGVjaWVzIH4gLiwgZGF0YT1pcmlzLCBpbXBvcnRhbmNlPVRSVUUsCiAgICAgICAgICAgICAgICAgICAgICAgIHByb3hpbWl0eT1UUlVFKQpwcmludChpcmlzLnJmKQpgYGAKCmBgYHtyfQojIyBMb29rIGF0IHZhcmlhYmxlIGltcG9ydGFuY2U6CnJvdW5kKGltcG9ydGFuY2UoaXJpcy5yZiksIDIpCmBgYAoKCiMgRXhlcmNpc2UgSUkKClVzaW5nIHJhbmRvbSBmb3Jlc3QgcmVncmVzc2lvbiwgcHJlZGljdCB0aGUgaG91c2luZyBwcmljZXMgaW4gdGhlIGBCb3N0b25gIApkYXRhc2V0IHVzZWQgcHJldmlvdXNseSBmb3IgdGhlIGV4ZXJjaXNlIG9uIHRoZSBMYXNzbyByZWdyZXNzaW9uLgoKMS4gRmlyc3QgdGhlIHJhbmRvbSBmb3Jlc3QgbW9kZWwgd2l0aCBkZWZhdWx0IHBhcmFtZXRlcnMKMi4gQ29tcHV0ZSB0aGUgTVNFIGZvciB0aGUgbW9kZWwgYW5kIGNvbXBhcmUgd2l0aCB0aGUgb25lIGZyb20gTGFzc28gcmVncmVzc2lvbi4gCjMuIFBsb3QgdGhlIHByZWRpY3RlZCB2YWx1ZXMgYW5kIHRoZSB0cnVlIG1lZGlhbiBob3VzZSB2YWx1ZXMgZm9yIHRoZSB0ZXN0IGRhdGEuCjQuIFBsb3QgYW5kIGluc3BlY3QgdGhlIHZhcmlhYmxlIGltcG9ydGFuY2UuIERvIHRoZXkgYWdyZWUgd2l0aCB0aGUgY29lZmZpY2llbnRzCmZvdW5kIGluIExhc3NvIHJlZ3Jlc3Npb24/CgpgYGB7cn0KZGF0YShCb3N0b24pCnNldC5zZWVkKDEyMykKdHJhaW5JZHggPC0gc2FtcGxlKDE6bnJvdyhCb3N0b24pLCByb3VuZCgwLjcgKiBucm93KEJvc3RvbikpKQpoZWFkKEJvc3RvbikKYGBgCgpgYGB7cn0KIyAoLi4uPykKYGBgCgoKIyBEaW1lbnNpb25hbCBSZWR1Y3Rpb24KCiogVG9kYXkgbW9zdCBvZiB0aGUgZGF0YXNldHMgYXJlIGhpZ2gtZGltZW5zaW9uYWwsIAogIGUuZy4gZ2VuZXRpYyBzZXF1ZW5jaW5nIGRhdGEgd2l0aCB0aG91c2FuZHMgb2YgZ2VuZXMgYW5kIGh1bmRyZWRzIG9mIHJvd3MsCiAgbWVkaWNhbCByZWNvcmRzIGRhdGEsIHVzZXIgaW50ZXJuZXQgYWN0aXZpdHkgZGF0YSBldGMuCiogRGltZW5zaW9uYWwgcmVkdWN0aW9uIG9yIGZlYXR1cmUgZXh0cmFjdGlvbiByZWR1Y2VzIHRoZSBudW1iZXIgb2YgCnZhcmlhYmxlcyB1bmRlciBjb25zaWRlcmF0aW9uLgoqIFRoaXMgcHJvY2VzcyBpcyB1c2VmdWwgZm9yOgogICAgKyBkYXRhIGNvbXByZXNzaW9uCiAgICArIHJlbW92aW5nIG5vaXNlIGFuZCByZWR1bmRhbnQgZmVhdHVyZXMKICAgICsgaW5jcmVhc2VzIHRoZSBhY2N1cmFjeSBvZiBvZiBkYXRhIGFuYWx5c2lzIG1ldGhvZHMgYnkgYXZvaWRpbmcgb3Zlci1maXR0aW5nCiogQ29tbW9uIG1ldGhvZHMgZm9yIGRpbWVuc2lvbmFsaXR5IHJlZHVjdGlvbiBpbmNsdWRlOgogICAgKyBwcmluY2lwYWwgY29tcG9uZW50IGFuYWx5c2lzIChQQ0EpLCAKICAgICsgaW5kZXBlbmRlbnQgY29tcG9uZW50IGFuYWx5c2lzIChJQ0EpLCAKICAgICsgbGluZWFyIGFuZCBub25saW5lYXIgbXVsdGlkaW1lbnNpb25hbCBzY2FsaW5nIChNRFMpCiAgICArIGFuZCBtYW55IG90aGVycwoKIyMgUHJpbmNpcGFsIENvbXBvbmVudCBBbmFseXNpcyAoUENBKQoKQW4gZXhhbXBsZSBmcm9tIEVTTCBDaGFwdGVyIDE0OgoKIVtdKC4vZmlndXJlcy9oYWxmU3BoZXJlLnBuZykKIVtdKC4vZmlndXJlcy9wY2EucG5nKQoKIyMgUENBIEV4YW1wbGU6IFVTIGNyaW1lIHJhdGVzCgpOb3cgd2Ugd2lsbCBkbyBhbiBleGFtcGxlIHVzaW5nIHRoZSBidWlsdCBpbiBkYXRhc2V0IG9uIHZpb2xlbnQgY3JpbWUgcmF0ZXMKaW4gdGhlIFVTIGZyb20gMTk3NS4KClRoZSBjb2RlIGlzIGFkYXB0ZWQgZnJvbSBJU0wuCgpgYGB7cn0KP1VTQXJyZXN0cwpoZWFkKFVTQXJyZXN0cykKc3RhdGVzIDwtIHJvdy5uYW1lcyhVU0FycmVzdHMpCmBgYAoKTWVhbiBhbmQgdmFyaWFuY2Ugb2YgdGhlIGNyaW1lIHJhdGVzIGFjcm9zcyBhbGwgc3RhdGVzOgpgYGB7cn0KYXBwbHkoVVNBcnJlc3RzLCAyLCBtZWFuKQphcHBseShVU0FycmVzdHMsIDIsIHZhcikKYGBgCgpDb21wdXRlIGEgUENBOgoKSW4gUiB5b3UgY2FuIHVzZSB0aGUgZnVuY3Rpb24gYHByY29tcCgpYCB0byBkbyBQQ0EuIENoZWNrIHRoZSBoZWxwIHBhZ2UKYD9wcmNvbXBgIGZvciBkZXRhaWxzLgoKPiBUaGUgY2FsY3VsYXRpb24gaXMgZG9uZSBieSBhIHNpbmd1bGFyIHZhbHVlIGRlY29tcG9zaXRpb24gb2YgdGhlIAooY2VudGVyZWQgYW5kIHBvc3NpYmx5IHNjYWxlZCkgZGF0YSBtYXRyaXgsIG5vdCBieSB1c2luZyBlaWdlbiBvbiAKdGhlIGNvdmFyaWFuY2UgbWF0cml4LiBUaGlzIGlzIGdlbmVyYWxseSB0aGUgcHJlZmVycmVkIG1ldGhvZCBmb3IgbnVtZXJpY2FsIAphY2N1cmFjeS4gVGhlIHByaW50IG1ldGhvZCBmb3IgdGhlc2Ugb2JqZWN0cyBwcmludHMgdGhlIHJlc3VsdHMgaW4gYSBuaWNlIApmb3JtYXQgYW5kIHRoZSBwbG90IG1ldGhvZCBwcm9kdWNlcyBhIHNjcmVlIHBsb3QuCgpgcHJjb21wKClgIGlzIGEgcHJlZmVycmVkIG1ldGhvZCBvdmVyIGBwcmluY29tcGAuCgpgYGB7cn0KcHIub3V0IDwtIHByY29tcChVU0FycmVzdHMsIHNjYWxlPVRSVUUpCm5hbWVzKHByLm91dCkKcHIub3V0JGNlbnRlcgpwci5vdXQkc2NhbGUKcHIub3V0JHJvdGF0aW9uCmRpbShwci5vdXQkeCkKYGBgCgpUaGUgb3V0cHV0IG9mIGBwcmNvbXAoKWAgaXMgYSBsaXN0IGNvbnRhaW5pbmcgdGhlIGZvbGxvd2luZzoKCiogYHNkZXZgOgl0aGUgc3RhbmRhcmQgZGV2aWF0aW9ucyBvZiB0aGUgcHJpbmNpcGFsIGNvbXBvbmVudHMgCihpLmUuLCB0aGUgc3F1YXJlIHJvb3RzIG9mIHRoZSBlaWdlbnZhbHVlcyBvZiB0aGUgY28tdmFyaWFuY2UvY29ycmVsYXRpb24gbWF0cml4LApYXlRYKQoqIGByb3RhdGlvbmA6CXRoZSBtYXRyaXggb2YgdmFyaWFibGUgbG9hZGluZ3MgKGkuZS4sIGEgbWF0cml4IHdob3NlIGNvbHVtbnMgCmNvbnRhaW4gdGhlIGVpZ2VudmVjdG9ycykuIAoqIGB4YDogdGhlIHZhbHVlIG9mIHRoZSByb3RhdGVkIGRhdGEgKHRoZSBjZW50ZXJlZCAoYW5kIHNjYWxlZCBpZiByZXF1ZXN0ZWQpIApkYXRhIG11bHRpcGxpZWQgYnkgdGhlIHJvdGF0aW9uIG1hdHJpeCkgaXMgcmV0dXJuZWQuIAoqIGBjZW50ZXIsIHNjYWxlYAl0aGUgY2VudGVyaW5nIGFuZCBzY2FsaW5nIHVzZWQsIG9yIEZBTFNFCgoKKipFYWNoIHByaW5jaXBhbCBjb21wb25lbnQgbG9hZGluZyBhbmQgc2NvcmUgdmVjdG9yIGlzIHVuaXF1ZSwgdXAgdG8gYSBzaWduIGZsaXAqKgoKYGBge3IgZmlnLmhlaWdodD01fQpiaXBsb3QocHIub3V0LCBzY2FsZT0wLCBjZXggPSAwLjgpCmBgYAoqKkVhY2ggcHJpbmNpcGFsIGNvbXBvbmVudCBsb2FkaW5nIGFuZCBzY29yZSB2ZWN0b3IgaXMgdW5pcXVlLCB1cCB0byBhIHNpZ24gZmxpcCoqClNvIGFub3RoZXIgc29mdHdhcmUgb2YgUiBwYWNrYWdlIGNvdWxkIGUuZy4gcmV0dXJuIHRoaXMgcGxvdCBpbnN0ZWFkOgoKYGBge3IgZmlnLmhlaWdodD01fQpwci5vdXQkcm90YXRpb249LXByLm91dCRyb3RhdGlvbgpwci5vdXQkeD0tcHIub3V0JHgKYmlwbG90KHByLm91dCwgc2NhbGU9MCwgY2V4ID0gMC44KQpgYGAKCiogdGhlIGZpcnN0IGxvYWRpbmcgdmVjdG9yIHBsYWNlcyBhcHByb3guIGVxdWFsIHdlaWdodCBvbiBgQXNzYXVsdGAsIGBNdXJkZXJgLCAKYW5kIGBSYXBlYCwgd2l0aCBtdWNoIGxlc3Mgd2VpZ2h0IG9uIGBVcmJhblBvcGAuIEhlbmNlIHRoaXMgY29tcG9uZW50IHJvdWdobHkgCmNvcnJlc3BvbmRzIHRvIGEgbWVhc3VyZSBvZiBvdmVyYWxsIHJhdGVzIG9mIHNlcmlvdXMgY3JpbWVzLiAKKiBUaGUgc2Vjb25kIGxvYWRpbmcgdmVjdG9yIHBsYWNlcyBtb3N0IG9mIGl0cyB3ZWlnaHQgb24gYFVyYmFuUG9wYC4gSGVuY2UsIGl0CnJvdWdobHkgY29ycmVzcG9uZHMgdG8gdGhlIGxldmVsIG9mIHVyYmFuaXphdGlvbiBvZiB0aGUgc3RhdGUuCiogVGhlIGNyaW1lLXJlbGF0ZWQgdmFyaWFibGVzIGFyZSBsb2NhdGVkIGNsb3NlIHRvIGVhY2ggb3RoZXIsIGFuZCB0aGF0IApgVXJiYW5Qb3BgIGlzIGZhciBmcm9tIHRoZW0uIAoqIFRoZSBjcmltZS1yZWxhdGVkIHZhcmlhYmxlcyBhcmUgY29ycmVsYXRlZCB3aXRoIGVhY2ggb3RoZXIsIGFuZCB0aGF0IAp0aGUgYFVyYmFuUG9wYCB2YXJpYWJsZSBpcyBsZXNzIGNvcnJlbGF0ZWQgd2l0aCB0aGUgb3RoZXIgdGhyZWUuCgoKIyMgQSBzY3JlZSBwbG90CgoqKkNob29zZSB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHByaW5jaXBhbCBjb21wb25lbnRzIHRoYXQgYXJlIHJlcXVpcmVkIGluIG9yZGVyIHRvIGV4cGxhaW4gYSBzaXphYmxlIGFtb3VudCBvZiB0aGUgdmFyaWF0aW9uIGluIHRoZSBkYXRhLioqCgpMb29rIGZvciBhIHBvaW50IGF0IHdoaWNoIHRoZSBwcm9wb3J0aW9uIG9mIHZhcmlhbmNlIGV4cGxhaW5lZCBieSBlYWNoCnN1YnNlcXVlbnQgcHJpbmNpcGFsIGNvbXBvbmVudCBkcm9wcyBvZmYuIFRoaXMgaXMgb2Z0ZW4gcmVmZXJyZWQgdG8gYXMgYW4KKmVsYm93KiBpbiB0aGUgc2NyZWUgcGxvdAoKYGBge3J9CnByLm91dCRzZGV2CnByLnZhciA8LSBwci5vdXQkc2Rldl4yCnByLnZhcgpwdmUgPC0gcHIudmFyL3N1bShwci52YXIpCnB2ZQpwbG90KHB2ZSwgeGxhYj0iUHJpbmNpcGFsIENvbXBvbmVudCIsIHlsYWI9IlByb3BvcnRpb24gb2YgVmFyaWFuY2UgRXhwbGFpbmVkIiwgeWxpbT1jKDAsMSksdHlwZT0nYicpCmBgYAoKCiMjIE11bHRpZGltZW5zaW9uYWwgU2NhbGluZyAoTURTKQoKPiBNRFMgYWxnb3JpdGhtIGFpbXMgdG8gcGxhY2UgZWFjaCBvYmplY3QgaW4gTi1kaW1lbnNpb25hbCBzcGFjZSBzdWNoIHRoYXQgCnRoZSBiZXR3ZWVuLW9iamVjdCBkaXN0YW5jZXMgYXJlIHByZXNlcnZlZCBhcyB3ZWxsIGFzIHBvc3NpYmxlLiBFYWNoIG9iamVjdCAKaXMgdGhlbiBhc3NpZ25lZCBjb29yZGluYXRlcyBpbiBlYWNoIG9mIHRoZSBOIGRpbWVuc2lvbnMuIFRoZSBudW1iZXIgCm9mIGRpbWVuc2lvbnMgb2YgYW4gTURTIHBsb3QgTiBjYW4gZXhjZWVkIDIgYW5kIGlzIHNwZWNpZmllZCBhIHByaW9yaS4gCkNob29zaW5nIE49MiBvcHRpbWl6ZXMgdGhlIG9iamVjdCBsb2NhdGlvbnMgZm9yIGEgdHdvLWRpbWVuc2lvbmFsIHNjYXR0ZXJwbG90LgoKVGhlcmUgYXJlIGRpZmZlcmVudCB0eXBlcyBvZiBNRFMgbWV0aG9kcyBpbmNsdWRpbmcsICpDbGFzc2ljYWwgTURTKiwKKk1ldHJpYyBNRFMqIGFuZCAqTm9uLW1ldHJpYyBNRFMqLiBUaGUgZGV0YWlscyBvbiB0aGUgZGlmZmVyZW5jZXMKY2EgYmUgZm91bmQgb246CgoqIFtXaWtpXShodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9NdWx0aWRpbWVuc2lvbmFsX3NjYWxpbmcpIHBhZ2Ugb24gTXVsdGlkaW1lbnNpb25hbCBTY2FsaW5nLgoqIFtBcHBsaWVkIE11bHRpZGltZW5zaW9uYWwgU2NhbGluZ10oaHR0cDovL3d3dy5zcHJpbmdlci5jb20vdXMvYm9vay85NzgzNjQyMzE4NDc0KQpib29rIGJ5IEJvcmcsIEdyb2VuZW4sIGFuZCBNYWlyIChDaGFwdGVyIDgpIAoKIyMgTURTIEV4YW1wbGU6IENvbG9yIHBlcmNlcHRpb24KCkVrbWFuIHN0dWRpZWQgaG93IHBlb3BsZSBwZXJjZWl2ZSBjb2xvcnMuIEhlIGNvbGxlY3RlZCBkYXRhIHdoZXJlIDMxIHN1YmplY3RzCnJhdGVkIHRoZSBzaW1pbGFyaXR5IHBmIGVhY2ggcGFpciBvZiAxNCBjb2xvcnMgb24gYSBhIDUtcG9pbnQgc2NhbGUgCigwID0gbm8gc2ltaWxhcml0eSwgNCA9IGlkZW50aWNhbCkuIEFmdGVyIGF2ZXJhZ2luZyB0aGUgMjEgc2ltaWxhcml0aWVzCnJhdGluZ3Mgd2VyZSBkaXZpZGVkIGJ5IDQgdG8gdHJhbnNmb3JtIHRoZW0gaW50byBhIHVuaXQgaW50ZXJ2YWwuClRoZSAxNCBjb2xvcnMgc3R1ZGllZCBoYWQgd2F2ZWxlbmd0aHMgYmV0d2VlbiA0MzQgYW5kIDY3NCBubS4KCmBgYHtyfQpla21hblNpbSA8LSByZWFkUkRTKCIuL2RhdGEvZWttYW4ucmRzIikKIyBjb252ZXJ0IHNpbWlsYXJpdGllcyB0byBkaXNzaW1pbGFyaXRpZXMKZWttYW5EaXN0IDwtIDEtIGVrbWFuU2ltCndhdmVsZW5ndGhzIDwtIHJvdW5kKHNlcSggNDM0LCA2NzQsIGxlbmd0aC5vdXQgPSAxNCkpCmBgYAoKVXNlIGBjbWRzY2FsZSgpYCBidWlsdC1pbiBmdW5jdGlvbiBmb3IgY2xhc3NpY2FsIE1EUy4gCk1ldHJpYyBpdGVyYXRpdmUgTURTIGFuZCBub24tbWV0cmljIE1EUyBmdW5jdGlvbiBhcmUgYXZhaWxhYmxlIGluIGEKcGFja2FnZSBgc21hY29mYCBhbmQgb3RoZXIgcGFja2FnZXMgYXJlIGFsc28gY29tcGFyZWQgCltoZXJlXShodHRwOi8vZ2FzdG9uc2FuY2hlei5jb20vaG93LXRvLzIwMTMvMDEvMjMvTURTLWluLVIvKS4KCmBgYHtyfQpla21hbk1EUyA8LSBjbWRzY2FsZShla21hbkRpc3QsIGsgPSAyKQpgYGAKCmBgYHtyIGZpZy5oZWlnaHQ9NSwgZmlnLndpZHRoPTUuNX0KcmVzIDwtIGRhdGEuZnJhbWUoZWttYW5NRFMpCnJlcyR3YXZlbGVuZ3RoIDwtIGZhY3Rvcih3YXZlbGVuZ3RocywgbGV2ZWxzID0gd2F2ZWxlbmd0aHMpCmdncGxvdChyZXMsIGFlcyhYMSwgWDIpKSArIGdlb21fcG9pbnQoKSArIHRoZW1lX2J3KCkgKwogIGdlb21fdGV4dChhZXMobGFiZWwgPSB3YXZlbGVuZ3RoKSwgaGp1c3Q9MC41LCB2anVzdD0tMSwgc2l6ZSA9IDMpCmBgYAoKSSBtYXBwZWQgdGhlIHdhdmVsZW5ndGhzIHRvIGhleGFkZWNpbWFsIGNvbG9ycyB1c2luZyB0aGlzIApbd2Vic2l0ZV0oaHR0cHM6Ly9hY2FkZW1vLm9yZy9kZW1vcy93YXZlbGVuZ3RoLXRvLWNvbG91ci1yZWxhdGlvbnNoaXAvKS4gCmBgYHtyfQpjb2xvcnNERiA8LSBkYXRhLmZyYW1lKAogIHdhdmVsZW5ndGggPSB3YXZlbGVuZ3RocywKICBoZXggPSBjKCIjMjgwMGZmIiwgIiMwMDUxZmYiLCAiIzAwYWVmZiIsICIjMDBmYmZmIiwgIiMwMGZmMjgiLCAiIzRlZmYwMCIsCiAgICAgICAgICAiIzkyZmYwMCIsICIjY2NmZjAwIiwgIiNmZmY5MDAiLCAiI2ZmYmUwMCIsICIjZmY3YjAwIiwgIiNmZjMwMDAiLAogICAgICAgICAgIiNmZjAwMDAiLCAiI2ZmMDAwMCIpKQpnZ3Bsb3QocmVzLCBhZXMoWDEsIFgyKSkgKyAKICBnZW9tX3BvaW50KGFlcyhjb2xvciA9IHdhdmVsZW5ndGgpLCBzaXplID0gMikgKyB0aGVtZV9idygpICsKICBnZW9tX3RleHQoYWVzKGxhYmVsID0gd2F2ZWxlbmd0aCksIGhqdXN0PTAuNSwgdmp1c3Q9LTEsIHNpemUgPSAzKSArCiAgc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IGFzLmNoYXJhY3Rlcihjb2xvcnNERiRoZXgpKQpgYGAKCioqTURTIHJlcHJvZHVjZXMgdGhlIHJlY29nbml6YWJsZSAyRCBjb2xvciB3aGVlbCoqCgojIyB0LURpc3RyaWJ1dGVkIFN0b2NoYXN0aWMgTmVpZ2hib3IgRW1iZWRkaW5nICh0U05FKQoKV2hhdCBpcyAqKnRTTkUqKj8KCiogKmEgdGVjaG5pcXVlIGZvciBkaW1lbnNpb25hbGl0eSByZWR1Y3Rpb24gdGhhdCBpcyBwYXJ0aWN1bGFybHkgd2VsbCBzdWl0ZWQgZm9yIHRoZSB2aXN1YWxpemF0aW9uIG9mIGhpZ2gtZGltZW5zaW9uYWwgZGF0YXNldHMuKl5baHR0cHM6Ly9sdmRtYWF0ZW4uZ2l0aHViLmlvL3RzbmUvXSAKKiB0aGUgbWV0aG9kIHdhcyBmaXJzdCBpbnRyb2R1Y2VkIGJ5IEwuSi5QLiB2YW4gZGVyIE1hYXRlbiBpbiAyMDA4LiBUaGUgb3JpZ2luYWwgCnBhcGVyIGlzIGF2YWlsYWJsZSBbaGVyZV0oaHR0cHM6Ly9sdmRtYWF0ZW4uZ2l0aHViLmlvL3B1YmxpY2F0aW9ucy9wYXBlcnMvSk1MUl8yMDA4LnBkZikKKiB0LVNORSB0cmllcyB0byBncm91cCBsb2NhbCBkYXRhIHBvaW50cyBjbG9zZXIgdG8gZWFjaCBvdGhlciwgaW5zdGVhZCBvZgp0cnlpbmcgdG8gcHJlc2VydmUgdGhlIGdsb2JhbCBzdHJ1Y3R1cmUgbGlrZSBtYW55IGRpbWVuc2lvbmFsaXR5IHJlZHVjdGlvbiAKdGVjaG5pcXVlcy4KCiMjIHRTTkUgRXhhbXBsZTogTWFzcyBjeXRvbWV0cnkKClRoZSBmb2xsb3dpbmcgZXhhbXBsZSBzaG93cyBob3cgdG8gY2FsY3VsYXRlIGFuZCBwbG90IGEgMkQgdC1TTkUgcHJvamVjdGlvbgp1c2luZyB0aGUgQmFybmVzLUh1dC1TTkUgYWxnb3JpdGhtLCB1c2luZyB0aGUgYFJ0c25lYCBwYWNrYWdlIGZvciBSLiBUaGlzCmV4YW1wbGUgd2FzIHdvcmtlZCBvdXQgYnkgW0x1a2FzIFdlYmVyXShodHRwczovL2dpdGh1Yi5jb20vbG13ZWJlci9SdHNuZS1leGFtcGxlKS4KCiogVGhlIGRhdGFzZXQgdXNlZCBpcyB0aGUgbWFzcyBjeXRvbWV0cnkgb2YgaGVhbHRoeSBodW1hbiBib25lIG1hcnJvdyBkYXRhIHNldCAKIk1hcnJvdzEiLCBzZWVuIGluIEZpZ3VyZSAxYiBvZiBbQW1pciBldCBhbC4gKDIwMTMpXSggaHR0cDovL3d3dy5uY2JpLm5sbS5uaWguZ292L3B1Ym1lZC8yMzY4NTQ4MCkuIAoqIE1hc3MgY3l0b21ldHJ5IGlzIGEgcmVjZW50IGFkdmFuY2UgaW4gZmxvdyBjeXRvbWV0cnksIHdoaWNoIGFsbG93cyBleHByZXNzaW9uIApsZXZlbHMgb2YgdXAgdG8gNDAgcHJvdGVpbnMgcGVyIGNlbGwgdG8gYmUgbWVhc3VyZWQgaW4gaHVuZHJlZHMgb2YgY2VsbHMgcGVyIHNlY29uZC5eW2h0dHBzOi8vZ2l0aHViLmNvbS9sbXdlYmVyL1J0c25lLWV4YW1wbGVdIAoqIFRoaXMgZGF0YXNldCBwcm92aWRlcyBhbiBleGFtcGxlIG9mIGFuIGlkZWFsIHQtU05FIHByb2plY3Rpb24sIHdoZXJlIGNlbGxzIApmcm9tIGRpZmZlcmVudCBjZWxsIHBvcHVsYXRpb25zICh0eXBlcykgYXJlIGdyb3VwZWQgYXMgZGlzdGluY3QgY2x1c3RlcnMgb2YgCnBvaW50cyBpbiB0aGUgMi1kaW1lbnNpb25hbCBwcm9qZWN0aW9uLCBhbmQgdGhlcmUgaXMgY2xlYXIgdmlzdWFsIHNlcGFyYXRpb24gCmJldHdlZW4gY2x1c3RlcnMuCgpTb3VyY2UgY29kZTogW2dpdGh1YiBsaW5rXShodHRwczovL2dpdGh1Yi5jb20vbG13ZWJlci9SdHNuZS1leGFtcGxlL2Jsb2IvbWFzdGVyL1J0c25lX3ZpU05FX2V4YW1wbGVfTWFycm93MS5SI0w0NikKCmBgYHtyIGV2YWwgPSBGQUxTRSwgZWNobyA9IEZBTFNFfQojIGRhdCA8LSByZWFkLmNzdigiLi9kYXRhL2hlYWx0aHlIdW1hbkJvbmVNYXJyb3cuY3N2IikKIyBkYXRbMToxMCwgMTo2XQojIGRpbShkYXQpCiMgCiMgIyBzdWJzYW1wbGluZwojIG5zdWIgPC0gMTAwMAojIHNldC5zZWVkKDEyMykgICMgc2V0IHJhbmRvbSBzZWVkCiMgZGF0IDwtIGRhdFtzYW1wbGUoMTpucm93KGRhdCksIG5zdWIpLCBdCiMgZGltKGRhdCkKYGBgCgpgYGB7cn0KIyBTa2lwIHRoZSBibG9jayBhYm92ZSBpZiBpdCB0YWtlcyB0b28gbG9uZyB0byBsb2FkLgojIFRoZSBzdWJzZXR0ZWQgZGF0YSBoYXMgYmVlZCBwb3J2aWRlZCBpbiBhIHNtYWxsZXIgZmlsZQpkYXQgPC0gcmVhZC5jc3YoIi4vZGF0YS9oZWFsdGh5SHVtYW5Cb25lTWFycm93X3NtYWxsLmNzdiIpCmRpbShkYXQpCmRhdFsxOjEwLCAxOjZdCmBgYAoKCgpgYGB7cn0KIyBzZWxlY3QgMTMgcHJvdGVpbiBtYXJrZXJzIHRvIHVzZSBpbiBjYWxjdWxhdGlvbiBvZiB0LVNORSBwcm9qZWN0aW9uCiMgQ0QxMWIsIENEMTIzLCBDRDE5LCBDRDIwLCBDRDMsIENEMzMsIENEMzQsIENEMzgsIENENCwgQ0Q0NSwgQ0Q0NVJBLCBDRDgsIENEOTAKIyAoc2VlIEFtaXIgZXQgYWwuIDIwMTMsIFN1cHBsZW1lbnRhcnkgVGFibGVzIDEgYW5kIDIpCgpjb2xuYW1lc19wcm9qIDwtIGNvbG5hbWVzKGRhdClbYygxMSwgMjMsIDEwLCAxNiwgNywgMjIsIDE0LCAyOCwgMTIsIDYsIDgsIDEzLCAzMCldCmNvbG5hbWVzX3Byb2ogICMgY2hlY2sgY2FyZWZ1bGx5IQpgYGAKCmBgYHtyfQojIGFyY3NpbmggdHJhbnNmb3JtYXRpb24KIyAoc2VlIEFtaXIgZXQgYWwuIDIwMTMsIE9ubGluZSBNZXRob2RzLCAiUHJvY2Vzc2luZyBvZiBtYXNzIGN5dG9tZXRyeSBkYXRhIikKYXNpbmhfc2NhbGUgPC0gNQpkYXQgPC0gYXNpbmgoZGF0IC8gYXNpbmhfc2NhbGUpICAjIHRyYW5zZm9ybXMgYWxsIGNvbHVtbnMhIGluY2x1ZGluZyBldmVudCBudW1iZXIgZXRjCgojIHByZXBhcmUgZGF0YSBmb3IgUnRzbmUKZGF0IDwtIGRhdFssIGNvbG5hbWVzX3Byb2pdICAgICAgIyBzZWxlY3QgY29sdW1ucyB0byB1c2UKZGF0IDwtIGRhdFshZHVwbGljYXRlZChkYXQpLCBdICAjIHJlbW92ZSByb3dzIGNvbnRhaW5pbmcgZHVwbGljYXRlIHZhbHVlcyB3aXRoaW4gcm91bmRpbmcKZGltKGRhdCkKYGBgCgpgYGB7cn0KbGlicmFyeShSdHNuZSkKIyBydW4gUnRzbmUgKEJhcm5lcy1IdXQtU05FIGFsZ29yaXRobSkKIyB3aXRob3V0IFBDQSBzdGVwIChzZWUgQW1pciBldCBhbC4gMjAxMywgT25saW5lIE1ldGhvZHMsICJ2aVNORSBhbmFseXNpcyIpCnNldC5zZWVkKDEyMykgICMgc2V0IHJhbmRvbSBzZWVkCnJ0c25lX291dCA8LSBSdHNuZShhcy5tYXRyaXgoZGF0KSwgcGNhID0gRkFMU0UsIHZlcmJvc2UgPSBUUlVFKQpgYGAKCmBgYHtyfQojIHBsb3QgMkQgdC1TTkUgcHJvamVjdGlvbgpwbG90KHJ0c25lX291dCRZLCBhc3AgPSAxLCBwY2ggPSAyMCwgY29sID0gImJsdWUiLCAKICAgICBjZXggPSAwLjc1LCBjZXguYXhpcyA9IDEuMjUsIGNleC5sYWIgPSAxLjI1LCBjZXgubWFpbiA9IDEuNSwgCiAgICAgeGxhYiA9ICJ0LVNORSBkaW1lbnNpb24gMSIsIHlsYWIgPSAidC1TTkUgZGltZW5zaW9uIDIiLCAKICAgICBtYWluID0gIjJEIHQtU05FIHByb2plY3Rpb24iKQpgYGAKCgoKIyBFeGVyY2lzZSBJSUkKCkRvd25sb2FkIE1OSVNUIGRhdGEgb2YgdGhlIGRpZ2l0cyBpbWFnZXMgZnJvbSB0aGUgW0thZ2dsZSBjb21wZXRpdGlvbl0oaHR0cHM6Ly93d3cua2FnZ2xlLmNvbS9jL2RpZ2l0LXJlY29nbml6ZXIpLgpUaGUgY29kZSBpcyBhZGFwdGVkIGZyb20gdGhlIG9uZSBbaGVyZV0oaHR0cHM6Ly93d3cua2FnZ2xlLmNvbS9nb3NwdXJzZ28vZGlnaXQtcmVjb2duaXplci9jbHVzdGVycy1pbi0yZC13aXRoLXRzbmUtdnMtcGNhL2NvZGUpLiAKClRoZSBgLi9kYXRhL3RyYWluLmNzdmAgYW5kIGAuL2RhdGEvdGVzdC5jc3ZgIGZpbGVzIGFyZSBkYXRhIG9uIHRoZSAyOHgyOCBwaXhlbAppbWFnZXMgb2YgZGlnaXRzICgwLTkpLiBUaGUgZGF0YSBpcyBjb21wb3NlZCBvZjoKCiogYGxhYmVsYCBjb2x1bW4gZGVub3RpbmcgdGhlIGRpZ2l0IG9uIHRoZSBpbWFnZQoqIGBwaXhlbDBgIHRocm91Z2ggYHBpeGVsNzgzYCBjb250YWluIGluZm9ybWF0aW9uIG9uIHRoZSBwaXhlbCBpbnRlbnNpdHkKKG9uIHRoZSBzY2FsZSBvZiAwLTI1NSksIGFuZCB0b2dldGhlciBmb3JtIHRoZSB2ZWN0b3JpemVkIHZlcnNpb24gb2YgCnRoZSAyOHgyOCBwaXhlbCBkaWdpdCBpbWFnZQoKIVtdKC4vZmlndXJlcy9tbmlzdEV4YW1wbGVzLnBuZykKCmBgYHtyIGV2YWwgPSBGQUxTRSwgZWNobyA9IEZBTFNFfQojICMgVGhlIGNvbXBldGl0aW9uIGRhdGFmaWxlcyBhcmUgaW4gdGhlIGRpcmVjdG9yeSAuLi9pbnB1dAojICMgUmVhZCBjb21wZXRpdGlvbiBkYXRhIGZpbGVzOgojIHRyYWluIDwtIHJlYWQuY3N2KCIuL2RhdGEvdHJhaW4uY3N2IikKIyB0ZXN0IDwtIHJlYWQuY3N2KCIuL2RhdGEvdGVzdC5jc3YiKQojIHRyYWluJGxhYmVsIDwtIGFzLmZhY3Rvcih0cmFpbiRsYWJlbCkKIyAKIyAjIHNocmlua2luZyB0aGUgc2l6ZSBmb3IgdGhlIHRpbWUgbGltaXQKIyBudW1UcmFpbiA8LSAxMDAwCiMgc2V0LnNlZWQoMTIzNCkKIyByb3dzIDwtIHNhbXBsZSgxOm5yb3codHJhaW4pLCBudW1UcmFpbikKIyB0cmFpbiA8LSB0cmFpbltyb3dzLF0KIyB3cml0ZS5jc3YodHJhaW4sICIuL2RhdGEvdHJhaW5fc21hbGwuY3N2IikKYGBgCgpgYGB7cn0KIyBTa2lwIHRoZSBwcmV2aW91cyBibG9jayBhbmQgbG9hZCB0aGUgYWxyZWFkeSBzdWJzZXR0ZWQgdHJhaW5pbmcgZGF0YSAoZmFzdGVyKS4KdHJhaW4gPC0gcmVhZC5jc3YoIi4vZGF0YS90cmFpbl9zbWFsbC5jc3YiKQpkaW0odHJhaW4pCmBgYAoKCjEuIENvbXB1dGUgdFNORSBlbWJlZGRpbmcgb2YgdGhlIHRyYWluaW5nIGRhdGEuCjIuIFZpc3VhbGl6ZWQgdGhlIHRTTkUgMkQgcHJvamVjdGlvbiB3aXRoIHRoZSBkaWdpdCBsYWJlbHMgYW5kIGNvbG9yaW5nLgozLiBQZXJmb3JtIGEgcHJpbmNpcGFsIGNvbXBvbmVudCBhbmFseXNpcyBvbiB0aGUgdHJhaW5pbmcgZGF0YS4KNC4gUGxvdCB0aGUgc2FtcGxlIHRoZSBQQ0Egc2NvcmVzIHdpdGggdGhlIGRpZ2l0IGxhYmVscyBhbmQgY29sb3JpbmcuCgpgYGB7cn0KIyAoLi4uID8pCmBgYAoKCioqV2hhdCBkbyB5b3Ugb2JzZXJ2ZT8gSG93IGRvZXMgdFNORSBjb21wYXJlIHdpdGggUENBIGluIHRoaXMgY2FzZT8qKgoKCiMgQ2x1c3RlciBBbmFseXNpcwoKKiAqKkNsdXN0ZXJpbmcqKiBpcyBhbiBleHBsb3JhdG9yeSB0ZWNobmlxdWUgd2hpY2ggZW5hYmxlcyB1cyB0byBmaW5kIGhpZGRlbiAKZ3JvdXBzIHRoYXQgY2FuIGJlIGltcG9ydGFudCBpbiBpbnRlcnByZXRpbmcgdGhlIGRhdGEuCiogR3JvdXBpbmdzIGFyZSBkZXRlcm1pbmVkIGZyb20gdGhlIGRhdGEgaXRzZWxmLCB3aXRob3V0IGFueSBwcmlvciBrbm93bGVkZ2UKYWJvdXQgb2JzZXJ2YXRpb25zIGxhYmVscyBvciBjbGFzc2lmaWNhdGlvbi4KCiFbXSguL2ZpZ3VyZXMvY2x1c3RlcnMucG5nKQoKKiBUbyBjbHVzdGVyIHRoZSBkYXRhIHdlIG5lZWQgYSAqKm1lYXN1cmUgb2Ygc2ltaWxhcml0eSoqIG9yCioqZGlzc2ltaWxhcml0eSoqIGJldHdlZW4gYSBwYWlyIG9mIG9ic2VydmF0aW9ucywgZS5nLiAgYW4gRXVjbGlkZWFuIGRpc3RhbmNlLgoKIVtdKC4vZmlndXJlcy9iaXJkc09mRmVhdGhlci5wbmcpCgpDaGVjayBvdXQgY2x1c3RlcmluZyBtZXRob2RzIGF2YWlsYWJsZSBvbiAKW0NSQU5dKGh0dHBzOi8vY3Jhbi5yLXByb2plY3Qub3JnL3dlYi92aWV3cy9DbHVzdGVyLmh0bWwpLgoKIyMgay1tZWFucwoKKiBrLW1lYW5zIGlzIGEgc2ltcGxlICppdGVyYXRpdmUgcmVsb2NhdGlvbiBtZXRob2QqIGZvciBjbHVzdGVyaW5nIGRhdGEgCmludG8gJGskIGRpc3RpbmN0IG5vbi1vdmVybGFwcGluZyBncm91cHMuIAoqIFRoZSBhbGdvcml0aG0gbWluaW1pemVzIHRoZSB2YXJpYXRpb24gd2l0aGluIGVhY2ggY2x1c3Rlci4KCkRlbW9uc3RyYXRpb24gb2YgaG93IGstbWVhbnMgY2x1c3RlcmluZyB3b3JrcyBjYW4gYmUgZm91bmQgaW4gdGhpcwpbYW5pbWF0aW9uXShodHRwOi8vc2hhYmFsLmluL3Zpc3VhbHMva21lYW5zLzIuaHRtbCkKCkRyYXdiYWNrczoKCiogVGhlIG51bWJlciBjbHVzdGVycyAkayQgbXVzdCBiZSBzcGVjaWZpZWQgYmVmb3JlIGNsdXN0ZXJpbmcuCiogRWFjaCB0aW1lIHRoZSBhbGdvcml0aG0gaXMgcnVuLCB0aGUgY2VudGVycyBvZiB0aGUgY2x1c3RlcnMgYXJlCnJhbmRvbWx5IGluaXRpYWxpemVkIGxlYWRpbmcgdG8gZGlmZmVyZW50IGZpbmFsIGNsdXN0ZXIgYXNzaWdubWVudHMuCgpUaGUgY2hvaWNlIG9mIHRoZSBudW1iZXIgb2YgY2x1c3RlcnMsICRrJCBjYW4gYmUgbWFkZSBieSBjb25zaWRlcmluZwpzdGF0aXN0aWNzIHN1Y2ggYXM6CgoqIEdhcCBTdGF0aXN0aWMgW2xpbmtdKGh0dHA6Ly93d3cud2ViLnN0YW5mb3JkLmVkdS9+aGFzdGllL1BhcGVycy9nYXAucGRmKQoqIFNpbGhvdWV0dGUgc3RhdGlzdGljIFtsaW5rXShodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9TaWxob3VldHRlXyhjbHVzdGVyaW5nKSkKKiBDYWxpbnNraS1IYXJiYXN6IGluZGV4IFtsaW5rXShodHRwOi8vd3d3LmJpb21lZGNlbnRyYWwuY29tL2NvbnRlbnQvc3VwcGxlbWVudGFyeS8xNDc3LTU5NTYtOS0zMC1TNC5QREYpCgoKIyMgay1tZWFucyBmb3IgaW1hZ2Ugc2VnbWVudGF0aW9uL2NvbXByZXNzaW9uCgpPbmUgb2YgdGhlIGFwcGxpY2F0aW9uIG9mIGstbWVhbnMgY2x1c3RlcmluZyBpcyAqKmltYWdlIHNlZ21lbnRhdGlvbioqLgpUaGUgY29kZSBwcm92aWRlZCBhcmUgYWRhcHRlZCBmcm9tIHRoZSBmb3VuZCAKW2hlcmVdKGh0dHBzOi8vd3d3LnItYmxvZ2dlcnMuY29tL3Itay1tZWFucy1jbHVzdGVyaW5nLW9uLWFuLWltYWdlLykuCgoKIyMjIERvd25sb2FkIGFuZCByZWFkIHRoZSBpbWFnZQoKRG93bmxvYWQgeW91ciBmYXZvcml0ZSBpbWFnZSAvIGRvIGEgcXVpY2sgR29vZ2xlIHNlYXJjaCBmb3Igb25lIC8gdXNlIHRoZSBvbmUgCnByb3ZpZGVkLiBNYWtlIHN1cmUgdGhhdCB5b3VyIHBpY3R1cmUgaXMgbm90IHRvbyBiaWcgKGUuZy4gYXJvdW5kIGlzIGZpbmUKNDAwIHggNjAwIHB4KS4gT3RoZXJ3aXNlLCB0aGUgY29kZSBtaWdodCB0YWtlIGEgd2hpbGUgdG8gcnVuLgoKVGhlIGltYWdlIHByb3ZpZGVkIGlzIGEgcGljdHVyZSBvZiBjb2xvcmZ1bCB0dWxpcHMgaW4gdGhlIE5ldGhlcmxhbmRzCmRvd25sb2FkZWQgZnJvbSBbaGVyZV0oaHR0cDovL3d3dy5pbmZvaG9zdGVscy5jb20vaW1tYWdpbmkvbmV3cy8yMTc5LmpwZykuCgoKYGBge3J9CmxpYnJhcnkoanBlZykKdXJsIDwtICJodHRwOi8vd3d3LmluZm9ob3N0ZWxzLmNvbS9pbW1hZ2luaS9uZXdzLzIxNzkuanBnIgoKIyBEb3dubG9hZCB0aGUgZmlsZSBhbmQgc2F2ZSBpdCBhcyAiSW1hZ2UuanBnIiBpbiB0aGUgZGlyZWN0b3J5CmRGaWxlIDwtIGRvd25sb2FkLmZpbGUodXJsLCAiLi9maWd1cmVzL0ltYWdlLmpwZyIpCmltZyA8LSByZWFkSlBFRygiLi9maWd1cmVzL0ltYWdlLmpwZyIpICMgUmVhZCB0aGUgaW1hZ2UKKGltZ0RtIDwtIGRpbShpbWcpKQpgYGAKCiMjIyBWZWN0b3JpemUgdGhlIGRhdGEgaW50byBSR0IgY2hhbm5lbHMKClJlcHJlc2VudCB0aGUgM0QgYXJyYXkgYXMgYSBkYXRhIGZyYW1lIHdpdGggZWFjaCByb3cgcmVwcmVzZW50aW5nIGEgc2luZ2xlCnBpeGVsLiBUaGUgY29sdW1ucyB4IGFuZCB5IGdpdmUgdGhlIHBpeGVsIGxvY2F0aW9uLCBhbmQgUiwgRywgQiBkZW5vdGUKdGhlIHBpeGVsIGludGVuc2l0eSBpbiByZWQsIGdyZWVuLCBibHVlIHJlc3BlY3RpdmVseS4KCmBgYHtyfQojIEFzc2lnbiBSR0IgY2hhbm5lbHMgdG8gZGF0YSBmcmFtZQppbWdSR0IgPC0gZGF0YS5mcmFtZSgKICB4ID0gcmVwKDE6aW1nRG1bMl0sIGVhY2ggPSBpbWdEbVsxXSksCiAgeSA9IHJlcChpbWdEbVsxXToxLCBpbWdEbVsyXSksCiAgUiA9IGFzLnZlY3RvcihpbWdbLCwxXSksCiAgRyA9IGFzLnZlY3RvcihpbWdbLCwyXSksCiAgQiA9IGFzLnZlY3RvcihpbWdbLCwzXSkKICApCmBgYAoKIyMjIFBsb3QgdGhlIGltYWdlCgpgYGB7cn0KIyBnZ3Bsb3QgdGhlbWUgdG8gYmUgdXNlZApwbG90VGhlbWUgPC0gZnVuY3Rpb24oKSB7CiAgdGhlbWUoCiAgICBwYW5lbC5iYWNrZ3JvdW5kID0gZWxlbWVudF9yZWN0KAogICAgICBzaXplID0gMywKICAgICAgY29sb3VyID0gImJsYWNrIiwKICAgICAgZmlsbCA9ICJ3aGl0ZSIpLAogICAgYXhpcy50aWNrcyA9IGVsZW1lbnRfbGluZSgKICAgICAgc2l6ZSA9IDIpLAogICAgcGFuZWwuZ3JpZC5tYWpvciA9IGVsZW1lbnRfbGluZSgKICAgICAgY29sb3VyID0gImdyYXk4MCIsCiAgICAgIGxpbmV0eXBlID0gImRvdHRlZCIpLAogICAgcGFuZWwuZ3JpZC5taW5vciA9IGVsZW1lbnRfbGluZSgKICAgICAgY29sb3VyID0gImdyYXk5MCIsCiAgICAgIGxpbmV0eXBlID0gImRhc2hlZCIpLAogICAgYXhpcy50aXRsZS54ID0gZWxlbWVudF90ZXh0KAogICAgICBzaXplID0gcmVsKDEuMiksCiAgICAgIGZhY2UgPSAiYm9sZCIpLAogICAgYXhpcy50aXRsZS55ID0gZWxlbWVudF90ZXh0KAogICAgICBzaXplID0gcmVsKDEuMiksCiAgICAgIGZhY2UgPSAiYm9sZCIpLAogICAgcGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dCgKICAgICAgc2l6ZSA9IDIwLAogICAgICBmYWNlID0gImJvbGQiLAogICAgICB2anVzdCA9IDEuNSkKICApCn0KYGBgCgpgYGB7cn0KIyBQbG90IHRoZSBpbWFnZQpnZ3Bsb3QoZGF0YSA9IGltZ1JHQiwgYWVzKHggPSB4LCB5ID0geSkpICsgCiAgZ2VvbV9wb2ludChjb2xvdXIgPSByZ2IoaW1nUkdCW2MoIlIiLCAiRyIsICJCIildKSkgKwogIGxhYnModGl0bGUgPSAiT3JpZ2luYWwgSW1hZ2U6IENvbG9yZnVsIEZsb3dlcnMiKSArCiAgeGxhYigieCIpICsKICB5bGFiKCJ5IikgKwogIHBsb3RUaGVtZSgpCmBgYAoKCiMjIyBrLW1lYW5zIGluIFIKCkNob29zZSB0aGUgbnVtYmVyIG9mIGNsdXN0ZXJzIChjb2xvcnMgaW4gdGhpcyBjYXNlKSBhbmQgZG8gay1tZWFucyBjbHVzdGVyaW5nIAp3aXRoIGBrbWVhbnMoKWAgYnVpbHQtaW4gZnVuY3Rpb24uCgpgYGB7cn0Ka0NsdXN0ZXJzIDwtIDIKa01lYW5zIDwtIGttZWFucyhpbWdSR0JbLCBjKCJSIiwgIkciLCAiQiIpXSwgY2VudGVycyA9IGtDbHVzdGVycykKa0NvbG91cnMgPC0gcmdiKGtNZWFucyRjZW50ZXJzW2tNZWFucyRjbHVzdGVyLF0pCmBgYAoKVGhlbiBwbG90IHRoZSByZXN1bHRzLgoKYGBge3J9CmdncGxvdChkYXRhID0gaW1nUkdCLCBhZXMoeCA9IHgsIHkgPSB5KSkgKyAKICBnZW9tX3BvaW50KGNvbG91ciA9IGtDb2xvdXJzKSArCiAgbGFicyh0aXRsZSA9IHBhc3RlKCJrLU1lYW5zIENsdXN0ZXJpbmcgb2YiLCBrQ2x1c3RlcnMsICJDb2xvdXJzIikpICsKICB4bGFiKCJ4IikgKwogIHlsYWIoInkiKSArIAogIHBsb3RUaGVtZSgpCmBgYAoKYGBge3J9CmtDbHVzdGVycyA8LSA2CmtNZWFucyA8LSBrbWVhbnMoaW1nUkdCWywgYygiUiIsICJHIiwgIkIiKV0sIGNlbnRlcnMgPSBrQ2x1c3RlcnMpCm5hbWVzKGtNZWFucykKa0NvbG91cnMgPC0gcmdiKGtNZWFucyRjZW50ZXJzW2tNZWFucyRjbHVzdGVyLF0pCmBgYAoKVGhlbiBwbG90IHRoZSByZXN1bHRzLgoKYGBge3J9CmdncGxvdChkYXRhID0gaW1nUkdCLCBhZXMoeCA9IHgsIHkgPSB5KSkgKyAKICBnZW9tX3BvaW50KGNvbG91ciA9IGtDb2xvdXJzKSArCiAgbGFicyh0aXRsZSA9IHBhc3RlKCJrLU1lYW5zIENsdXN0ZXJpbmcgb2YiLCBrQ2x1c3RlcnMsICJDb2xvdXJzIikpICsKICB4bGFiKCJ4IikgKwogIHlsYWIoInkiKSArIAogIHBsb3RUaGVtZSgpCmBgYAoKIyMgSGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcKCiFbQWxleGFuZGVyIENhbGRlcidzIG1vYmlsZV0oLi9maWd1cmVzL2NhbGRlck1vYmlsZS5qcGcpCgpJZiB5b3UgZG9uJ3Qgd2FudCB0byBzcGVjaWZ5IG9yIGlmIGl0IGlzIGhhcmQgdG8gY2hvb3NlIHRoZSBudW1iZXIgb2YgY2x1c3RlcnMKYmFzZWQgb24gdGhlIGRpYWdub3N0aWNzIHlvdSBjYW4gdHJ5ICoqaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcqKiwgd2hpY2gKcHJvdmlkZXMgYSBncmFwaGljYWwgdHJlZS1iYXNlZCByZXByZXNlbnRhdGlvbiBvZiB0aGUgZGF0YSwgY2FsbGVkIAphICoqZGVuZG9ncmFtKiosICB0aGF0IHdvdWxkIGFsbG93IHlvdSB0byBldmFsdWF0ZSB3aGVyZSB0aGUKY3V0b2ZmIGZvciBncm91cGluZyBzaG91bGQgb2NjdXIuCgpUaGUgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgYWxnb3JpdGhtIHN1bW1hcnkgaXMgZ2l2ZW4gYmVsb3cKCiFbXSguL2ZpZ3VyZXMvaGllcmFyY2hpY2FsQ2x1c3RlcmluZ0FsZ29yaXRobS5wbmcpCgpTb3VyY2U6IElTTAoKVGhlIHJlc3VsdHMgZm9yIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIHdpbGwgZGlmZmVyIGJhc2VkIG9uIHlvdXIgY2hvaWNlIG9mOgoKKiB0aGUgZGlzdGFuY2UgbWVhc3VyZSBiZXR3ZWVuIGEgcGFpciBvZiBvYnNlcnZhdGlvbnM6CiAgICArIEV1Y2xpZGVhbiwKICAgICsgTWFuaGF0dGFuLAogICAgKyBKYWNjYXJkCiAgICArIGV0Yy4gW2xpbmtdKGh0dHA6Ly9kYXRhYXNwaXJhbnQuY29tLzIwMTUvMDQvMTEvZml2ZS1tb3N0LXBvcHVsYXItc2ltaWxhcml0eS1tZWFzdXJlcy1pbXBsZW1lbnRhdGlvbi1pbi1weXRob24vKQoqIHRoZSBkaXNzaW1pbGFyaXR5IGJldHdlZW4gMiBjbHVzdGVycywgaS5lLiB0aGUgY3JpdGVyaWEgdGhhdCBpcyB1c2VkIGZvciAKZ3JvdXBpbmcgY2x1c3RlcnMgdGhhdCBoYXZlIGJlZW4gY29tcG9zZWQ6CiAgIVtdKC4vZmlndXJlcy9saW5rYWdlcy5wbmcpCgojIyBIaWVyYXJjaGljYWwgQ2x1c3RlcmluZyBFeGFtcGxlOiBJcmlzIGRhdGFzZXQKCkFnYWluLCB3ZSB3aWxsIHVzZSB0aGUgRmlzaGVyJ3MgSXJpcyBkYXRhc2V0IHVzZWQgYmVmb3JlIGluIHRoZSByYW5kb20gCmZvcmVzdCBzZWN0aW9uLiBXZSB3aWxsIHNob3cgdGhhdCB1c2luZyBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyBvZiB0aGUgb2JzZXJ2ZWQKYXR0cmlidXRlcyBvbmUgY2FuIGNsdXN0ZXIgZmxvd2VycyBpbnRvIGdyb3VwcyBjb3JyZXNwb25kaW5nIHRvIHRoZWlyIHNwZWNpZXMuCgpgYGB7cn0KP2lyaXMKaGVhZChpcmlzKQpgYGAKCldlIHdpbGwgdXNlIHRoZSBidWlsdC1pbiBmdW5jdGlvbiBgaGNsdXN0KClgIHRvIHBlcmZvcm0gaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcuCk9ubHkgdGhlIGRhdGEgb24gdGhlIHBldGFsIGRpbWVuc2lvbnMgd2lsbCBiZSB1c2VkIGZvciBjb21wdXRpbmcgdGhlIGRpc3RhbmNlcwpiZXR3ZWVuIGZsb3dlci4KCmBgYHtyfQo/aGNsdXN0CiMgV2UgdXNlIHRoZSBFdWNsaWRlYW4gZGlzdGFuY2UgZm9yIHRoZSBkaXNzaW1pbGFyaXRpZXMgYmV0d2VlbiBmbG93ZXJzCmRpc3RNYXQgPC0gZGlzdChpcmlzWywgMzo0XSkKCiMgV2UgdXNlIHRoZSAiY29tcGxldGUiIGxpbmthZ2UgbWV0aG9kIGZvciBjb21wdXRpbmcgdGhlIGNsdXN0ZXIgZGlzdGFuY2VzLgpjbHVzdGVycyA8LSBoY2x1c3QoZGlzdE1hdCwgbWV0aG9kID0gImNvbXBsZXRlIikKcGxvdChjbHVzdGVycykKYGBgCgpJbnNwZWN0aW5nIHRoZSBwbG90IHdlIHNlZSB0aGF0IGEgcmVhc29uYWJsZSBjaG9pY2Ugb2YgdGhlIG51bWJlciBvZiBjbHVzdGVycyBpcwplaXRoZXIgMyBvciA0LgoKYGBge3J9CnBsb3QoY2x1c3RlcnMpCmFibGluZShhID0gMiwgYiA9IDAsIGNvbCA9ICJibHVlIikKYWJsaW5lKGEgPSAzLCBiID0gMCwgY29sID0gImJsdWUiKQpgYGAKCkxldCdzIHBpY2sgMyBjbHVzdGVycy4gVG8gZ2V0IHRoZSBsZWF2ZXMvb2JzZXJ2YXRpb25zIAooZmxvd2VycyBpbiB0aGlzIGNhc2UpIGFzc2lnbm1lbnRzIHVzaW5nIG9ubHkgMyBjbHVzdGVycyBmcm9tCnRoZSAqY2hvcHBlZCogdHJlZSB3ZSBjYW4gdXNlIGEgYGN1dHJlZSgpYCBmdW5jdGlvbi4KCmBgYHtyfQooY2x1c3RlckN1dCA8LSBjdXRyZWUoY2x1c3RlcnMsIDMpKQpgYGAKCmBgYHtyfQp0YWJsZShjbHVzdGVyQ3V0LCBpcmlzJFNwZWNpZXMpCmBgYAoKRnJvbSB0aGUgdGFibGUgd2Ugc2VlIHRoYXQgdGhlIHNlbnRvc2EgYW5kIHZpcmdpbmljYSB3ZXJlIGNvcnJlY3RseSBhc3NpZ25lZCB0bwpzZXBhcmF0ZSBncm91cHMuIEhvd2V2ZXIsIHRoZSBtZXRob2QgaGFkIHByb2JsZW1zIHRvIGdyb3VwIHRoZSB2ZXJzaWNvbG9yCmZsb3dlcnMgaW50byBhIHNlcGFyYXRlIGNsdXN0ZXIuCgpXZSBjYW4gdHJ5IGFub3RoZXIgbGlua2FnZSBtZXRob2QgbGlrZSAiYXZlcmFnZSIgYW5kIHNlZSBpZiB3ZSBwZXJmb3JtIGJldHRlci4KCmBgYHtyfQo/aGNsdXN0CiMgV2UgdXNlIHRoZSBFdWNsaWRlYW4gZGlzdGFuY2UgZm9yIHRoZSBkaXNzaW1pbGFyaXRpZXMgYmV0d2VlbiBmbG93ZXJzCmRpc3RNYXQgPC0gZGlzdChpcmlzWywgMzo0XSkKCiMgV2UgdXNlIHRoZSAiY29tcGxldGUiIGxpbmthZ2UgbWV0aG9kIGZvciBjb21wdXRpbmcgdGhlIGNsdXN0ZXIgZGlzdGFuY2VzLgpjbHVzdGVycyA8LSBoY2x1c3QoZGlzdE1hdCwgbWV0aG9kID0gImF2ZXJhZ2UiKQpwbG90KGNsdXN0ZXJzKQpgYGAKSGVyZSB3ZSBjYW4gY2hvb3NlIDMgb3IgNSBjbHVzdGVyczoKYGBge3J9CnBsb3QoY2x1c3RlcnMpCmFibGluZShhID0gMS40LCBiID0gMCwgY29sID0gImJsdWUiKQphYmxpbmUoYSA9IDAuOCwgYiA9IDAsIGNvbCA9ICJibHVlIikKYGBgCgpBZ2FpbiB3ZSBjaG9vc2UgMyBjbHVzdGVycwoKYGBge3J9CmNsdXN0ZXJDdXQgPC0gY3V0cmVlKGNsdXN0ZXJzLCAzKQp0YWJsZShjbHVzdGVyQ3V0LCBpcmlzJFNwZWNpZXMpCmBgYAoKV2Ugc2VlIHRoYXQgdGhpcyB0aW1lIHdlIGRvIGEgbGl0dGxlIGJldHRlciBpbiBjbHVzdGVyaW5nIHRoZSB2ZXJzaWNvbG9ycwp0b2dldGhlci4KCgpXZSBub3cgcGxvdCB0aGUgZmxvd2VycyB1c2luZyBwZXRhbCBkaW1lbnNpb25zIGFzIGNvb3JkaW5hdGVzLCAKYW5kIHNob3cgdGhlaXIgY2x1c3RlciBhc3NpZ25tZW50IGFzIHdlbGwgYXMgY29sb3IgcG9pbnRzIGJ5IHNwZWNpZXMuCgpgYGB7ciBmaWcuaGVpZ2h0PTYsIGZpZy53aWR0aD02fQpnZ3Bsb3QoaXJpcywgYWVzKFBldGFsLkxlbmd0aCwgUGV0YWwuV2lkdGgpKSArIHRoZW1lX2J3KCkgKwogIGdlb21fdGV4dChhZXMobGFiZWwgPSBjbHVzdGVyQ3V0KSwgdmp1c3QgPSAtMSkgKyAKICBnZW9tX3BvaW50KGFlcyhjb2xvciA9IFNwZWNpZXMpKQpgYGAKCgoKCgoKCgoK